Implement Max Heap
Build a max-heap from scratch: push, pop-max, and heapify on a plain array.
- 1 <= number of operations <= 10⁵
- -10⁹ <= value <= 10⁹
- Operations: push, pop-max, heapify
Intuition
To implement max heap you need push, pop-max and heapify over a plain array. What makes a heap elegant is that a tree structure is implied entirely by arithmetic — there are no pointers and no allocated nodes.
A heap is a complete binary tree, meaning every level is full except possibly the last, which fills left to right. Completeness is what allows the tree to be flattened into an array with no gaps, and it fixes the relationships:
- Node i has children at 2i + 1 and 2i + 2, and its parent is at (i − 1) / 2.
The only invariant is that every parent is at least as large as its children. Note what this does not say: siblings are unordered, and a heap is not a sorted array. That weaker guarantee is precisely why operations cost O(log n) rather than O(n) — you only ever fix one root-to-leaf path.
Push appends at the end, which is the only position that preserves completeness, then sifts up: swap with the parent while the new value is larger. Pop takes the root, moves the last element there to keep the shape valid, then sifts down: swap with the larger child while smaller than it.
Building a heap from an existing array is the pleasant surprise. Running sift-down from the last internal node backwards is O(n), not O(n log n) — most nodes are near the leaves and sift down only a step or two.
A heap is an array pretending to be a tree: children of i live at 2i+1 and 2i+2, the parent at (i-1)//2. Insertion bubbles up, removal moves the last element to the root and sinks it down. Both operations restore the invariant along a single root-to-leaf path, which is why they're O(log n).
Approach
Before reading on: price up what the direct approach costs here, then ask why only the extreme element matters and the rest need no ordering. Aim for O(log n) per op time and O(1) extra space.
Map the tree onto an array
Children of index i sit at 2i + 1 and 2i + 2; the parent is at (i - 1) / 2 with integer division. Completeness is what makes this gap-free, so no pointers are needed and the array's cache behaviour is excellent.
Hold only the parent-child invariant
Every parent must be greater than or equal to both children. Siblings have no required order and the array is not sorted — the weakness of the invariant is the source of the speed, since restoring it touches one path rather than the whole structure.
Push by appending and sifting up
Add the value at the end, preserving completeness, then swap it with its parent while it is larger. The walk stops at the root or when the parent already dominates, so at most log n swaps.
Pop by swapping in the last element
Save the root as the answer, move the final element into position 0, and shrink the array. Moving the last element is what keeps the tree complete — taking a child instead would leave a hole in the middle and break the index arithmetic.
Sift down against the larger child
Repeatedly compare with both children and swap with the larger one while it exceeds the current value. Swapping with the smaller child would place a value above a larger sibling, silently violating the invariant while appearing to make progress.
Build in linear time
To heapify an existing array, run sift-down from index n/2 - 1 down to 0. This is O(n), not O(n log n) — half the nodes are leaves needing no work, and the cost per level falls faster than the node count rises.
Cost of the operations
Push and pop are O(log n) since each walks one root-to-leaf path; reading the maximum is O(1); building from an array is O(n). Space is O(n) with no per-node overhead at all, unlike a pointer-based tree.
Solution & live demo
Common pitfalls
Using the wrong parent formula
parent = i // 2
parent = (i - 1) // 2
i // 2 is the parent formula for a 1-indexed heap. With 0-based arrays the children of i are 2i+1 and 2i+2, which inverts to (i-1)//2. Mixing the conventions silently compares against the wrong node.
Removing the root directly on pop
a.pop(0)
top, last = a[0], a.pop() if a: a[0] = last; # sink down
pop(0) shifts every element — O(n) — and destroys the heap layout. The standard move is to lift the last element into the root and sink it, which touches only one path.
Comparing against i instead of the running best when sinking
if l < n and a[l] > a[i]: big = l if r < n and a[r] > a[i]: big = r
if l < n and a[l] > a[big]: big = l if r < n and a[r] > a[big]: big = r
The second test must run against the winner of the first, not the original parent. Comparing both to a[i] lets the right child overwrite a larger left child, so the smaller of the two is promoted and the heap property breaks.
Edge cases
Root is the last element — remove and return, no sift.
≥ comparisons make ties stable enough; heap order tolerates equals on either side.