iwantcoding.com
🔥 Daily 👥 Rooms 🏆 Top Log in Sign up

Heaps / Priority Queue

By · Reviewed & last updated · Part of Data Structures & Algorithms

A binary heap is a complete binary tree where each parent ≤ children (min-heap) or ≥ (max-heap). Backed by an array; push / pop are O(log n). The right shape for priority queues, top-k, schedulers, Dijkstra.

Heap operations + heapsort + top-K

EXAMPLE
// 1) Python — heapq is a min-heap, in-place on a list
import heapq
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
print(heapq.heappop(h))   # 1
print(heapq.heappop(h))   # 3

// Heapify an existing list — O(n) (faster than n pushes)
nums = [9, 4, 7, 1, 5, 2]
heapq.heapify(nums)       # nums is now a valid min-heap

// 2) Top-K largest — nlargest / nsmallest
heapq.nlargest(3,  nums)  # 3 biggest
heapq.nsmallest(3, nums)

// 3) Streaming top-K (memory-bounded)
import heapq
k = 3
heap = []
for n in iter_of_a_billion_numbers():
    if len(heap) < k:
        heapq.heappush(heap, n)
    elif n > heap[0]:
        heapq.heappushpop(heap, n)   # discard smallest in a single op
# heap = top-3 elements (unsorted)

// 4) Max-heap from heapq — negate values
for x in xs:
    heapq.heappush(h, -x)
biggest = -heapq.heappop(h)

// 5) Tuple keys — priority queue with secondary sort
pq = []
heapq.heappush(pq, (priority, counter, task))   # counter breaks ties stably

// 6) JavaScript — no built-in heap, write one (or use a library)
class MinHeap {
    constructor() { this.a = []; }
    size()   { return this.a.length; }
    peek()   { return this.a[0]; }
    push(v) {
        const a = this.a;
        a.push(v);
        let i = a.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (a[p] <= a[i]) break;
            [a[p], a[i]] = [a[i], a[p]];
            i = p;
        }
    }
    pop() {
        const a = this.a;
        if (!a.length) return undefined;
        const top = a[0];
        const last = a.pop();
        if (a.length) {
            a[0] = last;
            const n = a.length;
            let i = 0;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let s = i;
                if (l < n && a[l] < a[s]) s = l;
                if (r < n && a[r] < a[s]) s = r;
                if (s === i) break;
                [a[i], a[s]] = [a[s], a[i]];
                i = s;
            }
        }
        return top;
    }
}

// 7) Heap sort — O(n log n)
def heapsort(xs):
    h = list(xs)
    heapq.heapify(h)
    return [heapq.heappop(h) for _ in range(len(h))]

// 8) Real uses
//   - Dijkstra / A* — pop smallest tentative distance
//   - Task scheduler — pop earliest-deadline task
//   - K-way merge — k iterators, heap of (current_value, iterator)
//   - Stream median — two heaps (max-heap of lower half, min-heap of upper half)

Why it matters

For “top K of N items” with N huge, a size-K heap streams in O(N log K) memory-bounded — nothing else matches. heappushpop is the secret weapon: one atomic operation per item.

Tip: Tweak the snippet with Try it Yourself », then sit the quiz at the bottom of the page.

Example

Example
// Min-heap as an array. parent = (i-1)/2, children = 2i+1, 2i+2.
// Library-grade min-heap is easier — most ecosystems ship one. JS often uses npm's heap-js.
Try it Yourself »

Discussion

Loading…