EXTRACT-MAX(): swap root with last, shrink, SIFT-DOWN
PEEK(): return A[0] // O(1)
SIFT-UP(i): while i>0 and A[parent]<A[i]: swap, i=parent(i)
SIFT-DOWN(i,size): find largest child, swap if larger, recurse
BUILD-HEAP(A): for i=n/2-1 downto 0: SIFT-DOWN(i,n) // O(n)
parent(i)=(i-1)/2, left=2i+1, right=2i+2
Section 2 -- The Idea, Step by Step
Picture the line at a hospital emergency room. People aren't seen in the order they arrived -- the most urgent patient always goes next, no matter how late they walked in. A priority queue is exactly that kind of line: whatever has the highest priority comes out first. A heap is the clever trick a computer uses to run that line quickly, without re-sorting everybody every time someone new shows up.
The one rule (high school). Imagine the numbers stacked in a pyramid: one value on top, two "children" hanging under each value. A max-heap obeys a single rule -- every parent is at least as big as its two children. That alone guarantees the largest value sits right at the very top, ready to grab. Notice we never claim the whole pile is sorted: siblings and cousins can sit in any order. The pyramid is stored as a plain list, so for the item at position $i$ its children live at $2i+1$ and $2i+2$ and its parent is at $\lfloor (i-1)/2 \rfloor$ -- no arrows or pointers needed.
A worked count. To add a key, drop it at the end of the list and let it "bubble up," swapping with its parent whenever it is larger (SIFT-UP). A heap of 1000 items is only about $\log_2 1000 \approx 10$ levels tall, so an insert needs at most ~10 swaps, not 1000. To remove the maximum, take the top, move the last item into the empty top slot, and let it "sift down," trading places with its larger child until the rule holds again (SIFT-DOWN) -- again about 10 steps for 1000 items.
Why it scales (AP / college). Both SIFT-UP and SIFT-DOWN walk one root-to-leaf path, so INSERT and EXTRACT-MAX cost $O(\log n)$ while PEEK is $O(1)$. The surprise: turning a whole unsorted array into a heap all at once (BUILD-HEAP) costs only $O(n)$, not $O(n\log n)$, because most nodes live near the leaves where sift-down is nearly free -- the cost sums as $\sum_h (n/2^{h+1})\,h = O(n)$. This one structure powers heapsort, Dijkstra's shortest paths, A* search, Huffman coding, and operating-system task scheduling.
Try this in the panel above. Set the preset to Sorted and drag n to its maximum, then step through with Next and watch the Comparisons counter climb; switch to Reverse at the same n and compare -- how much work a structure does depends on its starting order. As you step, follow the highlighted line in the pseudocode panel to see which rule is firing, and use the index formulas ($2i+1$, $2i+2$) to point from any slot to its children in the pyramid.
Section 3 -- Complexity Analysis
Symbol
Meaning
n
Input size
T(n)
Time complexity function
h
Height or depth of structure
k
Key or rank parameter
W(n)
Worst-case complexity
A(n)
Average-case complexity
Step 1 -- Heap Property. Max-heap: A[parent] >= A[child] for all nodes. Min-heap: A[parent] <= A[child]. The implicit binary tree is stored in an array: parent at (i-1)/2, left child at 2i+1, right child at 2i+2.
Step 2 -- SIFT-UP cost. Insert at position n (end). Swap with parent while parent < new key. Path length = height = floor(log2 n). Cost: O(log n).
Step 3 -- SIFT-DOWN cost. Compare node with children, swap with larger child if smaller. Repeat downward. Path length <= height = floor(log2 n). Cost: O(log n). Used in EXTRACT-MAX and BUILD-HEAP.
Step 4 -- BUILD-HEAP O(n). Sigma_{h=0}^{log n} (n/2^{h+1}) * 2h = n * Sigma h/2^h = 2n. So O(n) total -- better than n insertions which would be O(n log n).
Step 5 -- Decrease-Key for Dijkstra. Decrease priority of existing element: update key, SIFT-UP. O(log n) if element's position is known (requires index tracking). Critical for Dijkstra's O((V+E) log V) implementation.
Max-heap: every parent >= its children. This guarantees A[0] is the maximum. It does NOT mean the array is sorted -- only the parent-child relationships are ordered.
Why is BUILD-HEAP O(n) not O(n log n)? complex+
Most nodes are near the bottom with cheap SIFT-DOWN. Half the nodes are leaves (height 0). Quarter at height 1. Harmonic series sum: n * Sigma_{h=0}^{log n} h/2^h converges to 2n. Contrast with top-down insertion: O(n log n).
Where are priority queues used in systems? applied+
OS process scheduling (run queue ordered by priority). Network packet routing (QoS priority). Dijkstra and A* pathfinding. Event-driven simulation (events by timestamp). Huffman coding (build tree using min-PQ).
Why is Fibonacci heap not used despite better O(1) decrease-key? nonobv+
Fibonacci heap has terrible constant factors and complex implementation. The O(1) amortized decrease-key only helps when decrease-key is called far more often than extract-min -- like dense graphs in Dijkstra. For sparse graphs, binary heap is faster in practice.
What does the simulation show? sim+
The simulation shows the array representation (bars) and implicitly the tree (each bar is a node at its heap index). Orange bars are being compared during SIFT operations. Green bar is the root (maximum). Watch how EXTRACT-MAX removes root, moves last element up, then sifts it back down.
How is min-heap related to max-heap? deep+
Min-heap: negate all values, use max-heap, negate back on extraction. Or: flip all comparison operators. C++ std::priority_queue is max-heap by default. For min-heap: use std::priority_queue, greater> or negate values.
Section 5 -- Common Misconceptions
Conceptual Misconceptions
X A max-heap is a sorted array.
O Max-heap only guarantees parent >= children. Siblings have no ordering. Only A[0] is guaranteed to be maximum.
X BUILD-HEAP by inserting one at a time is optimal.
O Top-down insertion: O(n log n). Bottom-up BUILD-HEAP: O(n). Bottom-up exploits cheap SIFT-DOWN near leaves.
X Heap supports O(log n) decrease-key directly.
O Standard binary heap does not support decrease-key efficiently without an index map. You must track each element's array index. Fibonacci heap supports O(1) amortized decrease-key without index tracking.
Implementation Errors
X Using 1-indexed array with formulas for 0-indexed heap.
O 0-indexed: parent=(i-1)/2, left=2i+1, right=2i+2. 1-indexed: parent=i/2, left=2i, right=2i+1. Mixing these is a very common bug.
X Forgetting to decrease heap size in EXTRACT-MAX.
O After swapping A[0] with A[end], heap size must become end (not end+1). SIFT-DOWN must use the reduced size or sorted elements get re-heapified.
X Calling SIFT-UP on newly inserted element is wrong when building heap.
O BUILD-HEAP uses SIFT-DOWN bottom-up, not SIFT-UP. Using SIFT-UP in BUILD-HEAP would give O(n log n) instead of O(n).