Heap and priority queue

Overview

A heap is a complete binary tree stored in an array that keeps the smallest (min-heap) or largest (max-heap) element at the root. Children of index i live at 2i + 1 and 2i + 2, and the parent at floor((i - 1) / 2). Push and pop are O(log n); peeking at the root is O(1).

A priority queue is the abstract idea (always remove the highest-priority item) and a heap is how it is implemented. Heaps power Dijkstra's shortest path, Prim's MST, top K problems, running medians, merging sorted streams, and task schedulers.

When to use it

• Repeatedly get the smallest or largest item while items are being added.
• Top K, kth largest, or k closest.
• Merging k sorted lists or streams.
• Scheduling by priority or earliest deadline.
• Greedy algorithms that always pick the cheapest next option (Dijkstra, Prim, Huffman).

Problem patterns it solves

Where it is used in real software

Key terms

Heap property

In a min-heap, every parent <= its children (root is the minimum).

Sift up (bubble up)

After push, swap the new element with its parent while it is smaller.

Sift down (heapify down)

After pop, move the last element to the root and swap it down with the smaller child.

Heapify

Build a heap from an array in O(n) by sifting down from the last parent to the root.

Complete binary tree

All levels full except possibly the last, which fills left to right; no gaps in the array.

Push and pop in a min-heap

1. 1
   Push: append at the end

   Place the new value at index n to keep the tree complete.

2. 2
   Push: sift up

   While the value is smaller than its parent at (i - 1) >> 1, swap them.

3. 3
   Pop: take the root

   The minimum is at index 0.

4. 4
   Pop: move the last element to the root

   This keeps the tree complete.

5. 5
   Pop: sift down

   Swap with the smaller child until both children are larger or it becomes a leaf.

Pop from the min-heap [1, 4, 2, 7, 5, 3]

Remove the minimum and restore the heap

Returned 1, and the new minimum 2 is at the root. The work is one path from root to leaf: O(log n).

Implementation

1class PriorityQueue {2  constructor(compare = (a, b) => a - b) {3    this.heap = [];4    this.compare = compare; // negative means a has higher priority5  }6  get size() { return this.heap.length; }7  peek() { return this.heap[0]; }8 9  push(value) {10    const h = this.heap;11    h.push(value);12    let i = h.length - 1;13    while (i > 0) {14      const parent = (i - 1) >> 1;15      if (this.compare(h[i], h[parent]) >= 0) break;16      [h[i], h[parent]] = [h[parent], h[i]];17      i = parent;18    }19  }20 21  pop() {22    const h = this.heap;23    if (h.length === 0) return undefined;24    const top = h[0];25    const last = h.pop();26    if (h.length > 0) {27      h[0] = last;28      let i = 0;29      for (;;) {30        const left = 2 * i + 1, right = left + 1;31        let best = i;32        if (left < h.length && this.compare(h[left], h[best]) < 0) best = left;33        if (right < h.length && this.compare(h[right], h[best]) < 0) best = right;34        if (best === i) break;35        [h[i], h[best]] = [h[best], h[i]];36        i = best;37      }38    }39    return top;40  }41}42 43// 295. Find Median from Data Stream with two heaps44class MedianFinder {45  constructor() {46    this.low = new PriorityQueue((a, b) => b - a); // max-heap: lower half47    this.high = new PriorityQueue();                // min-heap: upper half48  }49  addNum(num) {50    this.low.push(num);51    this.high.push(this.low.pop());           // keep every low <= every high52    if (this.high.size > this.low.size) this.low.push(this.high.pop());53  }54  findMedian() {55    return this.low.size > this.high.size56      ? this.low.peek()57      : (this.low.peek() + this.high.peek()) / 2;58  }59}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Assuming Java's PriorityQueue is a max-heap.

  Fix: It is a min-heap by default; pass Collections.reverseOrder() for max.

• Iterating a PriorityQueue expecting sorted order.

  Fix: Iteration order is the array order, not sorted. Poll repeatedly to get sorted output.

• Using sort after each insert in JavaScript.

  Fix: That is O(n log n) per insert. Implement or import a binary heap.

• Changing an element's priority in place.

  Fix: The heap will not re-order. Remove and re-insert, or push a new entry and lazily skip stale ones.

Interview questions

Practice problems