Binary Heap & Priority Queue

An emergency room, a CPU scheduler, Dijkstra’s algorithm: all of them keep asking “what is the most urgent item right now?”. A binary heap answers in O(1) and updates in O(log n), inside a plain array.

★ Lecture: tree_heap · Zaza Gamezardashvili▶ video intermediate⏱ 12 min read

←Builds on

5Trees: Concepts, Properties, TraversalsA heap is a complete binary tree where every parent is smaller than its children.1Arrays & Dynamic ArraysA heap lives in an array: the children of i sit at 2i+1 and 2i+2.3Queue (FIFO) & DequeA priority queue is a queue where the smallest leaves first instead of the oldest.

Leads to→

8Dijkstra's AlgorithmDijkstra keeps candidate distances in a min-heap.

1Learn 2Watch 3Play 4Check 5Practice

Learn

The idea, the mechanics and the cost.

01What a priority queue needs

A priority queue stores items with priorities and supports three operations: insert an item, peek at the smallest (or largest) one, and extract it. The obvious structures each fail somewhere:

a sorted array: cheap peek, but insertion shifts elements, O(n);
an unsorted array: O(1) insertion, but finding the minimum is O(n);
a balanced BST: O(log n) for everything, but heavy machinery for a job that only ever looks at one end.

The binary heap is the lightweight answer: peek in O(1), insert and extract in O(log n), no pointers, just an array. It powers std::priority_queue, Python’s heapq and Java’s PriorityQueue, and through them Dijkstra’s and Prim’s algorithms, event simulations, “k largest” queries and heapsort.

02Two rules: shape and order

A min-heap is a binary tree with two rules:

shape: the tree is complete: every level is full except possibly the last, which fills from the left;
order: every parent is ≤ its children, so the minimum always sits at the root.

The shape rule is what lets us drop the pointers. Number the vertices level by level from 0 and store them in an array: the children of index i are at 2i+1 and 2i+2, its parent at (i−1)/2. In the figure, 3 sits at index 1 and its children 7 and 5 at indices 3 and 4. A complete tree with n vertices has height ⌊log₂ n⌋, and that bounds every operation below.

Note what the order rule does not say: siblings are not sorted and neither is the array. A heap is only sorted enough to know its minimum.

The heap built from 7, 3, 9, 1, 5, 8, as a tree and as an array.

03Insert: sift up

To insert x, append it to the end of the array. The shape is still complete, but x may be smaller than its parent. So sift up: while x is smaller than its parent, swap the two. Each swap moves x one level higher and repairs the order rule on that edge; everything else was fine already.

Insert 2 into [1, 3, 8, 7, 5, 9]: it lands at index 6, under 8. 2 < 8, swap; its parent is now 1, and 2 > 1, stop. Result: [1, 3, 2, 7, 5, 9, 8]. At most one swap per level, so insert is O(log n).

Peek is just heap[0]: O(1). In C++ it is pq.top(), and pq.push(x) performs exactly this sift-up.

04Extract-min: sift down, and heapsort

To extract the minimum, take heap[0], move the last element into the root and shrink the array. The shape is fine again, but the new root is probably too big. Sift down: compare it with its children and swap it with the smaller one, until it is ≤ both children or becomes a leaf. Swapping with the smaller child matters: that child becomes the parent of the other one, so the rule holds.

From [1, 3, 8, 7, 5, 9]: remove 1, move 9 to the top → [9, 3, 8, 7, 5]; 9 > 3, swap → [3, 9, 8, 7, 5]; 9 > 5, swap → [3, 5, 8, 7, 9]. O(log n).

Two extras. Build-heap turns any array into a heap in O(n) by sifting down every index from n/2 − 1 to 0. Heapsort builds a heap and extracts n times: O(n log n) with no extra memory. In C++, priority_queue<int> is a max-heap; a min-heap is priority_queue<int, vector<int>, greater<int>>.

Cost at a glance

Peek minO(1)

Insert (sift up)O(log n)

Extract-min (sift down)O(log n)

Build-heap from an arrayO(n)

HeapsortO(n log n)

Remember

A heap keeps two rules: a complete shape, so it fits in an array with children at 2i+1 and 2i+2, and parent ≤ children.
Insert sifts up from the end and extract-min sifts down from the root; both touch one path, O(log n).
Use a heap when you repeatedly need the current minimum or maximum, not a fully sorted order.

Watch

The lecture as a narrated explainer video.

▶

Watch the lecture, animated

The video follows the lecture slide by slide: the same example, the same notation. Use it before or after playing with the visualizer.

▶ Open the video page ▣ Open as presentation

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the array strip under the tree: every swap in the tree is a swap of two array cells. Try your own numbers, for example a descending list.

Interactive visualizerfocus here, then space ← →

Min-heap (tree)

Array view (children at 2i+1, 2i+2)

Extracted (ascending)

∅

Insert 7 at the end (index 0). This keeps the tree “complete” (filled left to right, no holes).

Pseudocode

 1 binary min-heap: complete tree stored in an array 2 insert: append at end, then sift-up while < parent 3   (parent of i is at (i-1)/2) 4 peek min = heap[0]           // O(1) 5 extract-min: move last to root, 6   then sift-down while > a child

1 / 1

Check

Three questions. Pick an answer to see why.

In the array layout, where are the children of index 4?

Insert 0 into the min-heap [1, 3, 8, 7, 5, 9]. Where does 0 end up?

You need the 10 largest numbers from a stream of a million. Which approach is best?

Practice

Real problems to lock it in, easiest first.

LeetCodeLast Stone Weight beginner↗LeetCodeKth Largest Element in an Array intermediate↗LeetCodeTop K Frequent Elements intermediate↗CSESRoom Allocation intermediate↗LeetCodeFind Median from Data Stream advanced↗