Skip to content

Heaps and Priority Queues Deep Dive

Master binary heaps, heap operations, priority queues, and heap-sort.

What you'll learn

  • Binary heap properties and array representation
  • Heap operations: insert, extract, heapify
  • Priority queue applications
  • Heap-sort and its O(n log n) guarantee

Concept

Heaps and Priority Queues Deep Dive

A heap is a complete binary tree where each parent is <= (min-heap) or >= (max-heap) its children. The heap property ensures the minimum (or maximum) is always at the root, accessible in O(1).

Array Representation

A complete binary tree can be stored in an array without pointers: the children of index i are at 2i+1 and 2i+2, and the parent of i is at (i-1)/2 (integer division). This is cache-friendly (contiguous memory) and avoids pointer overhead.

Core Operations

insert (O(log n)): add at the end, then bubble up - swap with parent while heap property is violated. extractMin/Max (O(log n)): take the root, move the last element to the root, then sift down. heapify (O(n)): build a heap from an unordered array by sifting down from the middle index to 0.

Priority Queue

A priority queue is an abstract data type where each element has a priority; dequeue returns the highest-priority element. Heaps are the standard implementation. Applications: Dijkstra algorithm (extract-closest), Huffman coding (merge two least-frequent), event-driven simulation, task scheduling.

Heap-Sort

Heap-sort builds a heap in O(n), then repeatedly extracts the max into the back of the array. It is O(n log n) worst-case, in-place (O(1) extra space), but not stable. It is the only common sort that is both O(n log n) worst-case and in-place.

Example

              class PriorityQueue {
  constructor(compare = (a, b) => a < b) { this.h = []; this.compare = compare; }
  push(x) {
    this.h.push(x); let i = this.h.length - 1;
    while (i > 0) { const p = (i - 1) >> 1; if (!this.compare(this.h[i], this.h[p])) break; [this.h[i], this.h[p]] = [this.h[p], this.h[i]]; i = p; }
  }
  pop() {
    const top = this.h[0]; const last = this.h.pop();
    if (this.h.length > 0) {
      this.h[0] = last; let i = 0, n = this.h.length;
      while (true) { let s = i, l = 2*i+1, r = 2*i+2; if (l < n && this.compare(this.h[l], this.h[s])) s = l; if (r < n && this.compare(this.h[r], this.h[s])) s = r; if (s === i) break; [this.h[i], this.h[s]] = [this.h[s], this.h[i]]; i = s; }
    }
    return top;
  }
  get size() { return this.h.length; }
}
const pq = new PriorityQueue((a, b) => a.priority < b.priority);
pq.push({task: 'render', priority: 1}); pq.push({task: 'fetch', priority: 3}); pq.push({task: 'log', priority: 2});
while (pq.size) console.log(pq.pop().task);
            

The priority queue uses a comparison function to determine ordering. push bubbles up, pop sifts down. The task scheduler processes highest-priority tasks first.

Try it

  • Crontab Generator

    Scheduled jobs often use priority queues - see how priority affects execution order.

Common mistakes

The mistake

Using a sorted array instead of a heap for a priority queue.

The fix

A sorted array gives O(n) insert. A heap gives O(log n) insert and extract - use it for dynamic priority queues.

The mistake

Confusing min-heap and max-heap.

The fix

A min-heap root is the minimum; a max-heap root is the maximum. Be consistent - mixing them produces wrong results.

Look up unfamiliar terms

A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.

View glossary

Build real projects

Apply what you learned by building guided projects with starter code and solutions.

View projects

Decode error messages

Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.

View errors