Binary Heap Visualizer

How it works

1. Store the tree level by level in an array. For index i: left child 2i + 1, right child 2i + 2, parent ⌊(i − 1) / 2⌋.
2. Peek: the root a[0] is the maximum (or minimum). O(1).
3. Insert: append the key at a[n] so the tree stays complete, then sift up — swap it with its parent while it beats the parent.
4. Extract: save a[0], move the last key into the root, shrink the heap, then sift down — swap with the better child while a child beats it.
5. Build: sift down every internal node from ⌊n/2⌋ − 1 back to 0, which heapifies an arbitrary array in O(n).

Two rules: shape and order

Every binary heap maintains two invariants at once.

• Shape: the tree is complete — every level is full except possibly the last, which fills from left to right. A complete tree of n nodes has height ⌊log₂ n⌋, which is where every O(log n) bound comes from.
• Order (the heap property): in a max-heap every parent is ≥ each of its children; in a min-heap, ≤.

Notice what the order rule does not say. Siblings are unordered, and a key on the left side of the tree can be smaller than a key one level lower on the right. A heap is not sorted — the only guarantee runs along each root-to-leaf path. That weaker promise is exactly why heaps are cheaper to maintain than sorted arrays or search trees.

Why a heap lives in an array

Because the tree is complete, writing it out level by level leaves no gaps, so no pointers are needed: positions alone encode the structure. With 0-based indexing the children of i are 2i + 1 and 2i + 2 and its parent is ⌊(i − 1) / 2⌋; with the 1-based indexing common in textbooks they are 2i, 2i + 1 and ⌊i / 2⌋.

That makes heaps compact and fast — one contiguous block, no per-node allocation — and it is why the visualizer draws the tree and the array together. Hover any key and the same element lights up in both views, along with its parent and children.

Worked example: insert 70 into a max-heap

The page opens with a max-heap built from 35, 12, 48, 7, 61, 23, 9, 54, 18, 40. After the bottom-up build it is stored as [61, 54, 48, 35, 40, 23, 9, 7, 18, 12].

• Append: 70 goes to a[10], the next free slot. Its parent is a[⌊9 / 2⌋] = a[4] = 40.
• Sift up: 70 > 40, swap. At index 4 its parent is a[1] = 54; 70 > 54, swap. At index 1 its parent is a[0] = 61; 70 > 61, swap.
• Stop: 70 has reached the root. The heap is now [70, 61, 48, 35, 54, 23, 9, 7, 18, 12, 40].

Three swaps in a tree of height 3 — the worst case, because 70 is the new maximum. Insert 5 instead and it stays at the bottom with zero swaps; for random keys an insert moves only a constant number of levels on average.

Min-heap vs max-heap

The two are mirror images: the code is identical except for the direction of each comparison. Use a max-heap when you repeatedly need the largest key (in-place heap sort, keeping the k smallest items seen so far) and a min-heap when you need the smallest (Dijkstra's shortest paths, event schedulers, merging sorted streams).

Libraries pick different defaults. Python's heapq and Java's PriorityQueue are min-heaps; C++'s std::priority_queue is a max-heap. To get the other kind, negate numeric keys or pass a reversed comparator. The Min/Max switch in the visualizer rebuilds the current keys under the other rule so you can compare the two trees.

Heap vs sorted array vs balanced BST

All three can serve as a priority queue; they differ in what they pay for.

• Sorted array: O(1) minimum or maximum, but O(n) insert because elements shift.
• Balanced BST (AVL, red-black): O(log n) for everything, plus ordered iteration and search for any key — at the cost of pointers, rotations and more memory.
• Binary heap: O(1) peek, O(log n) insert and extract, O(n) build, no pointers. Searching for an arbitrary key is O(n), and there is no sorted iteration.

If you only ever need the extreme element, the heap does the least work. If you also need "find 42" or "everything between 10 and 20", use a search tree.

Common mistakes

• Mixing 0-based and 1-based formulas — 2i and 2i + 1 are the children only when the root sits at index 1.
• Swapping with the wrong child in sift-down. In a max-heap you must swap with the larger child; swapping with the smaller one puts a smaller key above a larger one.
• Assuming the array is sorted. Only a[0] is guaranteed. To get every key in order, extract repeatedly — that is heap sort.
• Building by repeated insertion when all keys are known up front. The bottom-up build is O(n) instead of O(n log n).

Time and space complexity

Binary Heap in Python

def peek_max(a):
    if not a:
        raise IndexError("empty heap")
    return a[0]  # the root, O(1)


def insert(a, key):
    a.append(key)  # a[n] ← key;  n ← n + 1
    sift_up(a, len(a) - 1)


def sift_up(a, i):
    # move a[i] up while it beats its parent
    while i > 0:
        p = (i - 1) // 2
        if a[p] >= a[i]:  # in order
            return
        a[i], a[p] = a[p], a[i]
        i = p


def extract_max(a):
    if not a:
        raise IndexError("empty heap")
    top = a[0]
    # swap(a[0], a[n − 1]);  n ← n − 1
    a[0], a[-1] = a[-1], a[0]
    a.pop()
    sift_down(a, 0, len(a))
    return top


def sift_down(a, i, n):
    # sink a[i] inside the heap a[0:n]
    while 2 * i + 1 < n:
        l, r = 2 * i + 1, 2 * i + 2
        largest = l
        if r < n and a[r] > a[l]:
            largest = r
        if a[i] >= a[largest]:  # in order
            return
        a[i], a[largest] = a[largest], a[i]
        i = largest

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Priority Queue VisualizerPriority queue visualizer: a binary heap always serves the top-priority item first. Watch insert, peek and extract in O(log n) and see how Dijkstra uses it.
• Heap Sort VisualizerHeap sort visualizer: build a max-heap, then swap the root to the end and sift down, step by step. O(n log n) worst case, in place but not stable, with code.
• Build Heap (Heapify) — Why It's O(n)Build-heap (heapify) turns an array into a binary heap in O(n) by sifting down from the last parent up to the root. Watch it and see why it beats n inserts.
• Dijkstra's Algorithm VisualizerDijkstra's algorithm finds the shortest paths from one node in a graph with non-negative weights. Watch every relaxation step by step, with heap-based code.
• Binary Search Tree VisualizerBinary search tree visualizer: insert, search and delete keys step by step, see why every operation costs O(h), and compare a plain BST with AVL and B-trees.