The Core Idea
A Weaker Rule Than a BST — On Purpose
A heap is a tree (almost always represented as an array, not with explicit node pointers) that enforces the heap property: in a min-heap, every parent is smaller than or equal to both its children; in a max-heap, every parent is larger than or equal to both its children. Crucially, there's no rule at all comparing siblings or cousins to each other — only the parent-child relationship matters.
This is deliberately weaker than a binary search tree's ordering rule, and that's the whole point: a BST guarantees full sorted order (expensive to maintain), while a heap only guarantees 'the extreme value is always at the root' (cheap to maintain), which is exactly the guarantee most real use cases actually need.
💡 Memory Trick
Picture a family hierarchy where every parent is guaranteed shorter than their own children (a min-heap) — but two siblings could be any height relative to each other, and cousins have no guaranteed relationship at all. The one thing you can always say for certain is that the shortest person in the entire family is sitting at the very top of the family tree, because every single parent-child link enforces 'parent is shorter.'
The Core Operations
Insertion and Extraction
1
Peek — O(1)
The minimum (or maximum) element is always at the root, so retrieving it without removing it is instant — just look at index 0 of the underlying array.
2
Insert — O(log n)
Add the new element at the next open spot at the bottom of the tree (the end of the underlying array), then 'sift up': repeatedly swap it with its parent as long as it violates the heap property, until it either reaches the root or finds a parent it's not smaller (min-heap) or larger (max-heap) than.
3
Extract Min/Max — O(log n)
Remove the root (the min or max), replace it with the very last element in the array, then 'sift down': repeatedly swap it with whichever of its children would violate the heap property, until it settles into a position where the property holds again.
4
Why Array-Based Representation Works
Because a heap is always a 'complete' binary tree (every level full except possibly the last, which fills left to right with no gaps), its structure can be stored efficiently in a plain array using simple index arithmetic: a node at index i has children at indices 2i+1 and 2i+2, and a parent at index (i-1)/2 — no pointers needed at all.
The Main Use Case
Priority Queues
A heap is the standard implementation behind a priority queue — a queue where elements are dequeued not by arrival order (like a normal queue) but by priority, always returning the current highest-priority (or lowest-cost) item first. This is exactly why Dijkstra's algorithm uses a min-heap internally: at each step, it needs to efficiently retrieve whichever unvisited node currently has the smallest known distance.
Heaps are also the basis of heap sort (repeatedly extracting the min or max to build a sorted output, in O(n log n)) and are used for problems like 'find the k smallest/largest elements' or 'merge k sorted lists,' wherever repeatedly retrieving an extreme value efficiently is the core requirement.
🖥️ Applied Scenario
You're building a hospital ER triage system where patients must be seen in order of medical urgency, not in order of arrival, and new patients are constantly being added.
1
You reject a plain queue, since it would serve patients strictly in arrival order — completely ignoring urgency, which is the whole point of triage.
2
You choose a min-heap (keyed by urgency score, where lower means more urgent), so the single most urgent patient is always instantly accessible at the root.
3
When a new patient arrives, you insert them with sift-up — O(log n) — correctly placing them without disturbing the heap property for anyone else.
4
Conclusion: every time a doctor becomes available, you extract-min in O(log n), always retrieving the currently most urgent waiting patient, which is exactly the priority-queue behavior a heap is built for.
📌 Exam Application
Exam questions frequently ask you to trace through inserting a sequence of values into a min-heap or max-heap, showing the sift-up swaps at each step, or to trace an extract-min/max operation showing the sift-down swaps. You may also be asked to compute a child or parent's array index given a node's index, testing your understanding of the array-based representation.
⚠️ Most Common Heaps Mistakes
The most common mistake is assuming a heap is fully sorted, the way a BST's in-order traversal is — a heap only guarantees the parent-child relationship, not any ordering between siblings or across different subtrees, so reading a heap's array left to right does NOT give you sorted order. Another frequent error is confusing which direction sift-up and sift-down compare — in a min-heap, sift-up stops once the new element's parent is smaller or equal, not once it 'looks about right'; the comparison direction must be flipped consistently for a max-heap.
✓ Quick Self-Test
Can you insert the sequence 5, 3, 8, 1, 9, 2 into a min-heap by hand, showing the sift-up swaps at each step? Can you explain why heap-based extraction is O(log n) while peeking at the min/max is O(1)?
→
← All Data Structures Lessons