Heaps and Priority Queues Visualized

Why a binary heap keeps the next priority at the root, maps naturally to an array, and supports efficient scheduling.

A priority queue answers a behavioral question: “which item has the most urgent priority?” A binary heap is a common implementation. A heap is not a sorted array and not a binary search tree. It makes one value easy to find—the minimum or maximum—while leaving siblings and distant branches only partially ordered.

Complete shape and heap property

A binary heap is a complete binary tree: levels are filled left to right, with only the last level possibly incomplete. That shape has no holes, so it maps directly into an array. For zero-based index $i$ :

\text{left}(i) = 2i + 1,\quad \text{right}(i) = 2i + 2,\quad \text{parent}(i) = \left\lfloor \frac{i - 1}{2} \right\rfloor

A min-heap maintains $\text{parent} \le \text{children}$ ; a max-heap maintains $\text{parent} \ge \text{children}$ . Notice what this does not say: an arbitrary value is not searchable in $O(\log n)$ .

💡

The tree and the array are two views of the same heap. Index arithmetic replaces child pointers because the tree is complete.

Insert, peek, and extract

To insert, append at the end to preserve completeness. Then compare with the parent and sift up until the property holds. To extract the root, move the last item to the root, remove the last slot, then sift down by exchanging with the better child. Each path has at most the tree height, $O(\log n)$ . Peek is $O(1)$ because the priority item is already at index 0.

TypeScript

function parent(index: number): number {
  return Math.floor((index - 1) / 2);
}

function pushMin(heap: number[], value: number): void {
  heap.push(value);

  for (let index = heap.length - 1; index > 0;) {
    const parentIndex = parent(index);
    if (heap[parentIndex] <= heap[index]) break;

    [heap[parentIndex], heap[index]] = [heap[index], heap[parentIndex]];
    index = parentIndex;
  }
}

Peek

O(1)

Insert

O(\log n)

Extract

O(\log n)

Build heap

O(n)

Operation	Binary heap	Why
Peek min/max	$O(1)$	root is index 0
Insert	$O(\log n)$	one upward path
Extract min/max	$O(\log n)$	one downward path
Bottom-up build	$O(n)$	most nodes are near leaves

Why heapify is O(n)

Building a heap by inserting $n$ items is $O(n \log n)$ . Bottom-up heapify instead starts at the last parent and sifts each parent down. Nodes near the bottom can move only a tiny distance, and there are many more of them than high nodes.

\sum_{h=0}^{\lfloor \log n \rfloor} \frac{n}{2^{h+1}} \cdot O(h) = O(n)

The few nodes that can travel far are outweighed by the many leaves that do no work, so bottom-up heap construction is $O(n)$ .

Use cases and boundaries

Dijkstra's algorithm repeatedly chooses the smallest tentative distance, making a min-priority queue central to its efficient form. Schedulers pick the next task, event simulations pick the next timestamp, and streaming systems keep a bounded set of best candidates.

Heaps are a poor fit for “find key 42” or “iterate in fully sorted order.” A hash table handles exact-key lookup; a BST handles ordered search; sorting material covers heap sort as an in-place sorting technique.

Common mistakes

Calling a heap fully sorted. Only parent/child relationships are guaranteed.
Using an array representation without preserving the complete-tree shape.
Using a queue in place of a priority queue for Dijkstra; discovery order is not smallest distance.
Claiming heapify is O(n log n) without distinguishing it from repeated insertion.

Summary

The heap's narrow invariant is exactly what makes it useful: the next priority is always at the root, while updates touch only a root-to-leaf path. The visualizer shows the array and tree as the same structure so those index formulas become concrete.

Interactive Visualizer

Loading visualizer...