Heaps and Heap Operations: Complete Beginner's Guide

A heap is a binary tree with two rules. First, it is complete: every level is full except the last, which fills left to right. Second, it follows the heap property: in a min-heap every parent is smaller than or equal to its children, so the smallest element always sits at the root; in a max-heap every parent is larger than or equal to its children, so the largest is at the root. Think of a tournament bracket with the winner floating to the top.

Heaps matter because they answer one question extremely fast: "what is the smallest (or largest) item right now?" Operating systems pick the next process with heaps, map apps find shortest routes with them, and they underpin priority queues.

Key Concepts

• Min-heap / max-heap: parent ≤ children (minimum at root) versus parent ≥ children (maximum at root).
• Complete binary tree: the heap's shape, letting it live in a plain array with no pointers.
• Sift up: after inserting at the end, swap the node with its parent until order holds — O(log n).
• Heapify (sift down): push a node down, swapping with its smaller (min-heap) child — O(log n).
• Extract-min / extract-max: remove the root, move the last element up, then heapify — O(log n).
• Build-heap: turn an arbitrary array into a heap in O(n), faster than n separate inserts.

Formulas

• Array indices (0-based): for node i, left child = 2i + 1, right child = 2i + 2, parent = (i − 1) // 2. For i = 4: children 9 and 10, parent 1.
• Height: floor(log2 n) for n elements — 1,000 elements fit in at most 9 levels.
• Insert / extract: O(log n) each, following one root-to-leaf path.
• Peek at min/max: O(1) — it is always at index 0.
• Build heap: O(n) by heapifying from the last parent down to the root.

Worked Example

Insert 40, 10, 30, 5, 20 into an empty min-heap. Insert 40 → [40]. Insert 10 → [40, 10]; 10 < 40, swap → [10, 40]. Insert 30 → [10, 40, 30]; 30 > 10, stays. Insert 5 → [10, 40, 30, 5]; 5 < 40, swap → [10, 5, 30, 40]; 5 < 10, swap → [5, 10, 30, 40]. Insert 20 → [5, 10, 30, 40, 20]; 20 > 10, stays. Final heap: [5, 10, 30, 40, 20], minimum 5 at the root. Now extract-min: remove 5, move 20 to the root → [20, 10, 30, 40]; 20 > smaller child 10, swap → [10, 20, 30, 40]; 20 < 40, stop. New minimum is 10. Every step touched only one path, never the whole tree.

Common Misconceptions

• "A heap is a sorted array." Wrong. Only the root is the extreme value; [5, 10, 30, 40, 20] is a valid min-heap but not sorted.
• "Finding any element in a heap is fast." Wrong. Only the min/max is O(1); arbitrary search is O(n) since there is no left/right ordering rule.
• "Heapsort needs extra memory." Wrong. It sorts in place with O(1) extra space by swapping the root with the last unsorted element.

Real-World Applications

• Priority queues: hospital triage and OS schedulers use heaps underneath.
• Dijkstra's shortest path: repeatedly extracts the nearest unvisited city from a min-heap.
• Heapsort: guaranteed O(n log n) sorting with O(1) extra space.
• Streaming medians: two heaps track the running median of live sensor data.

A heap is a tournament that never ends: the champion always sits at the root, and every update replays only the matches along one path. That is why the biggest or smallest item is always one step away.