Heaps and Priority Queues: Always Know the Best

The problem: who gets seen next?

Picture the emergency ward of a busy government hospital on a Monday night. A patient walks in with a sprained ankle. A few minutes later, someone arrives clutching their chest, struggling to breathe. Then a child with a mild fever. Then an ambulance rushes in a patient in cardiac arrest. The triage nurse cannot treat people in the order they walked through the door — that would mean the sprained ankle gets seen before the cardiac arrest, simply because it arrived first. Instead, at every single moment, the nurse must be able to answer one question instantly: of everyone currently waiting, who is the most critical right now? And that answer keeps changing, because new patients keep arriving with their own severity, and the "most critical" patient of five minutes ago may already have been treated and removed from the waiting pool.

This is exactly the problem a priority queue solves. It is not a queue in the everyday sense (first-come-first-served); it is a collection where every item carries a priority, and the only promise the structure makes is: "I can always hand you the highest-priority item, right now, no matter how many new items you've thrown at me in between." A heap is the data structure that keeps this promise efficiently. By the end of this chapter you will be able to build one by hand, code one from scratch, use Python's built-in heap module correctly, and explain precisely why it is faster than the obvious alternatives.

Why not just use an array?

Before inventing the heap, it is worth asking why we don't just keep patients in a plain array or list. There are two obvious approaches, and both have a serious weakness.

• Unsorted array. Adding a new patient is trivial — just append them to the end, which takes constant time. But finding the most critical patient means scanning every single entry to find the maximum, which takes time proportional to the number of waiting patients (n). If there are 500 patients logged in a busy ward's queue, the nurse's system would need to inspect all 500 severity scores just to find the worst one — over and over, every time someone new needs to be pulled out.
• Sorted array (most severe first). Now finding the most critical patient is instant — just look at the front. But inserting a new patient means finding the correct spot to keep the array sorted and shifting every element after it, which again takes time proportional to n in the worst case.

Neither extreme is good enough when both insertions and extractions happen constantly and n is large. We want an approach where both operations are fast — not instant, but fast enough that even with thousands of items, the cost per operation barely grows. That approach is the binary heap, and it achieves both insert and extract-the-best in time proportional to log₂(n) — for 1,000 patients, roughly 10 comparisons instead of 1,000.

The heap: a tree with exactly one rule

A binary heap is a binary tree with two properties, and it is worth being precise about both, because Grade 9 students often blur them together.

Shape property (complete binary tree): every level of the tree is completely filled, except possibly the last level, which is filled strictly from left to right with no gaps. You cannot have a node in the bottom row with an empty slot to its left. This shape rule has nothing to do with the values stored — it is purely about the tree's structure, and it is what allows a heap to be stored compactly in a plain array (more on this shortly).

Heap-order property (for a max-heap): the value stored at every node must be greater than or equal to the values stored at both of its children. Notice the word "every" — this rule applies not just at the root, but recursively at every single node in the tree, all the way down. A min-heap is the mirror image: every node's value must be less than or equal to its children's values, so the smallest element sits at the root instead of the largest. This chapter builds a max-heap throughout, since our motivating example (most severe patient first) wants the largest priority on top; everything works identically in reverse for a min-heap.

Notice what the heap-order property does not say: it says nothing about how a left child compares to a right child, and nothing about how two nodes in different branches of the tree compare to each other. The only guarantee is along any parent-to-child edge. This local, edge-by-edge guarantee is deliberately weaker than "the whole tree is sorted" — and that weakness is precisely what makes heaps fast. We will return to this point, because it is the single most common misconception students carry into their first data structures exam.

Storing a tree inside a plain array

Because a heap is always a complete binary tree, it never has "holes" — so instead of building it with node objects and left/right pointers (like a general binary tree), we can pack it into a single flat array, numbering the nodes level by level, left to right, starting from index 0. If a node sits at index i in this array, simple arithmetic tells you exactly where its parent and children live:

• parent(i) = (i - 1) // 2
• left(i) = 2*i + 1
• right(i) = 2*i + 2

The // symbol is integer (floor) division — it divides and drops any remainder, so 5 // 2 is 2, not 2.5. These three formulas are the entire "wiring diagram" of a heap. There are no pointers to store or follow; given any index, you compute its relatives with arithmetic. This is also why heaps are memory-efficient compared to linked tree structures — no extra space is spent on parent/child references.

The diagram below shows one specific max-heap two ways: as a tree, and as the flat array that represents it exactly. Read the caption's formula, then check the annotation at the bottom, which verifies the heap-order property for one node using the formulas above.

Inserting a value: append, then bubble up

Because a heap must stay a complete tree, a new value can only be added in one legal place: the next open slot in the array, which is the same as the next open slot at the bottom level of the tree, filled left to right. That part is easy — it's just array.append(value).

The problem is that this new value was dropped in at random and probably breaks the heap-order property with its new parent. So we fix it locally: compare the new value with its parent; if the child is bigger, swap them. This swap may now break the heap property one level higher up, so repeat: compare with the new parent, swap if needed, and keep climbing until either the value finds a parent bigger than itself, or it reaches the root. This process is called bubble-up (or sift-up), and because a complete tree with n nodes has a height of only about log₂(n), the value climbs at most log₂(n) steps — this is where the O(log n) insert cost comes from.

Let's build a max-heap from scratch by inserting 5, 13, 2, 25, 7, 17, 20 one at a time, tracing every bubble-up step:

• Insert 5 → [5]
• Insert 13 → append: [5,13]. Index 1's parent is index (1-1)//2=0, value 5. Since 13 > 5, swap → [13,5].
• Insert 2 → append: [13,5,2]. Index 2's parent is index 0, value 13. Since 2 > 13 is false, stop → [13,5,2].
• Insert 25 → append: [13,5,2,25]. Index 3's parent is index (3-1)//2=1, value 5. Since 25 > 5, swap → [13,25,2,5]. Now the 25 is at index 1; its parent is index 0, value 13. Since 25 > 13, swap → [25,13,2,5]. It has reached the root, so it stops.
• Insert 7 → append: [25,13,2,5,7]. Index 4's parent is index (4-1)//2=1, value 13. Since 7 > 13 is false, stop → [25,13,2,5,7].
• Insert 17 → append: [25,13,2,5,7,17]. Index 5's parent is index (5-1)//2=2, value 2. Since 17 > 2, swap → [25,13,17,5,7,2]. Now 17 is at index 2; its parent is index 0, value 25. Since 17 > 25 is false, stop.
• Insert 20 → append: [25,13,17,5,7,2,20]. Index 6's parent is index (6-1)//2=2, value 17. Since 20 > 17, swap → [25,13,20,5,7,2,17]. Now 20 is at index 2; its parent is index 0, value 25. Since 20 > 25 is false, stop.

Final heap array: [25, 13, 20, 5, 7, 2, 17]. Every insertion required at most a handful of comparisons — never a full re-scan of the array.

Removing the best: extract-max and sift down

The maximum is always sitting at index 0, so peeking at it is a single array lookup — O(1), no searching required. Removing it is trickier, because deleting index 0 directly would leave a hole and break the array's compact shape. The standard trick: move the very last element in the array into the root's position, then shrink the array by one (removing that now-duplicated last slot). This instantly restores the complete-tree shape, but the value now sitting at the root is almost certainly not the maximum anymore, so we must restore the heap-order property — this time working downward, called sift-down (or bubble-down): compare the node with both of its children, and if either child is larger, swap with the larger of the two children (swapping with the smaller one would leave the heap property violated against the bigger child). Repeat down that path until the node is bigger than both its children, or it has no children left.

Trace extracting the max from [25, 13, 20, 5, 7, 2, 17]:

• Return the root, 25. Move the last element (17) into the root slot and shrink the array: [17, 13, 20, 5, 7, 2].
• Sift down from index 0 (value 17). Its children are index 1 (13) and index 2 (20). The larger child is 20. Since 20 > 17, swap with index 2 → [20, 13, 17, 5, 7, 2].
• Now 17 is at index 2. Its left child is index 5 (value 2); it has no right child (index 6 doesn't exist in a 6-element array). Since 2 > 17 is false, stop.

Resulting heap after one extraction: [20, 13, 17, 5, 7, 2], returned value 25. Just like insertion, this cost at most log₂(n) comparisons — the sift-down only ever travels one path from root to leaf, never touching the rest of the tree.

Common misconception: "a heap is basically a sorted array"

Look again at the array we just built: [25, 13, 20, 5, 7, 2, 17]. If you were told this represents a max-heap, it would be natural to expect the numbers to appear roughly in decreasing order — but 20 comes before 13 breaks nothing (13 is a different branch), yet notice 17 sits at the very end, after 5, 7, and 2, even though 17 is bigger than all three. This is not a bug. The heap-order property only constrains parent-child pairs along tree edges; it says absolutely nothing about how a node compares to a node in a completely different branch, or about the array being sorted overall. Students who have just learned binary search trees often import the wrong mental model here: in a BST, an in-order traversal always yields sorted values, so it feels natural to assume a heap array should be "mostly sorted" too. It is not. A heap gives you exactly one strong guarantee — instant access to the single best element — and deliberately gives up everything else, including the ability to binary-search the array for an arbitrary value, or to read off the second-largest element without doing further work. If you need the 2nd largest, you cannot just look at index 1 or index 2; you would have to extract the max once and then peek again. That trade-off — sacrificing global order for a fast, cheaply-maintained local guarantee — is the entire design idea behind a heap.

Coding a MaxHeap in Python

Translating the two traces above into working code gives a complete, minimal max-heap. Read it against the two traces — every line maps directly onto a step we already did by hand.

class MaxHeap:
    def __init__(self):
        self.data = []

    def parent(self, i):
        return (i - 1) // 2

    def left(self, i):
        return 2 * i + 1

    def right(self, i):
        return 2 * i + 2

    def insert(self, value):
        self.data.append(value)
        i = len(self.data) - 1
        while i > 0 and self.data[self.parent(i)] < self.data[i]:
            p = self.parent(i)
            self.data[p], self.data[i] = self.data[i], self.data[p]
            i = p

    def extract_max(self):
        if not self.data:
            return None
        top = self.data[0]
        last = self.data.pop()
        if self.data:
            self.data[0] = last
            self._sift_down(0)
        return top

    def _sift_down(self, i):
        n = len(self.data)
        while True:
            l, r = self.left(i), self.right(i)
            largest = i
            if l < n and self.data[l] > self.data[largest]:
                largest = l
            if r < n and self.data[r] > self.data[largest]:
                largest = r
            if largest == i:
                break
            self.data[i], self.data[largest] = self.data[largest], self.data[i]
            i = largest


h = MaxHeap()
for v in [5, 13, 2, 25, 7, 17, 20]:
    h.insert(v)
print(h.data)             # [25, 13, 20, 5, 7, 2, 17]
print(h.extract_max())    # 25
print(h.data)              # [20, 13, 17, 5, 7, 2]

Every value printed matches the hand traces exactly, which is the whole point of tracing by hand first — the code is not magic, it's just the bubble-up and sift-down rules written precisely enough for the computer to follow.

Python's built-in heapq — and the tie-breaking trick

You will rarely write your own heap class in practice, because Python ships one: the heapq module. There is one detail that trips up almost every student the first time: heapq only implements a min-heap — heapq.heappop always returns the smallest item, not the largest. If you want max-heap behaviour, the usual trick is to store negated numbers, or — more commonly in real problems — you want the smallest value to genuinely mean "highest priority" in the first place, such as a rank where 1 is best.

This is exactly the situation with a railway waiting list. When a confirmed passenger cancels a berth, the seat should go to whoever is closest to confirmation — the passenger with the smallest pending waitlist (WL) number gets it first. If two passengers ever ended up tied on the same priority, a sensible tie-break is whoever's request was logged earliest. This is a natural fit for heapq: push tuples of (priority, tiebreaker, name), and Python's tuple comparison does the rest — it compares the first elements, and only looks at the second element if the first ones are equal, exactly like comparing (subject-marks, roll-number) pairs on a merit list.

import heapq

waitlist = []
heapq.heappush(waitlist, (7, 143022, "Priya"))
heapq.heappush(waitlist, (3, 143501, "Arjun"))
heapq.heappush(waitlist, (7, 142959, "Meera"))
heapq.heappush(waitlist, (1, 144210, "Karan"))

while waitlist:
    wl_number, timestamp, name = heapq.heappop(waitlist)
    print(f"WL/{wl_number} -> {name}")

# Output:
# WL/1 -> Karan
# WL/3 -> Arjun
# WL/7 -> Meera
# WL/7 -> Priya

Trace why this order comes out: Karan has WL number 1, the smallest, so he pops first. Arjun is next at WL 3. Then come the two WL-7 entries, Priya and Meera — since their first tuple element ties at 7, Python compares the second element, the timestamp; Meera's 142959 is smaller (earlier) than Priya's 143022, so Meera pops before Priya even though Priya was pushed onto the heap first. The order things were pushed in never matters — only the tuple values decide the pop order. This tuple trick — (primary key, tiebreaker, payload) — is the standard way to build a priority queue with deterministic tie-breaking in Python, and it appears constantly in scheduling and simulation code.

Where heaps show up in graph algorithms

This chapter sits under graph algorithms for a reason: heaps are the engine inside some of the most important graph algorithms you will meet next. Dijkstra's shortest-path algorithm — the kind of algorithm behind turn-by-turn navigation apps — repeatedly needs to ask "of all the nodes I haven't finalized yet, which one currently has the smallest known distance from the start?" That is precisely the priority-queue question, and Dijkstra's algorithm becomes efficient specifically because a min-heap answers it in O(log n) instead of the O(n) a naive scan would need. The same idea powers Prim's algorithm for building a minimum spanning tree, and heaps are also the basis of an entire sorting technique, heap sort: build a max-heap out of every element (n insertions), then repeatedly extract the max and place it at the end of a growing sorted section — n extractions. Both phases cost O(log n) per operation across n elements, giving heap sort its overall O(n log n) running time, with the useful bonus that it needs no extra array, unlike merge sort.

How fast, exactly?

• Find the current best (peek): O(1) for a heap — always the root. O(n) for an unsorted array. O(1) for a sorted array.
• Insert a new item: O(log n) for a heap. O(1) for an unsorted array. O(n) for a sorted array (must shift to keep order).
• Remove the current best (extract): O(log n) for a heap. O(n) for an unsorted array (must search first). O(1) for a sorted array (front, but the array needed O(n) work to insert it correctly in the first place).
• Building a heap from n raw items by inserting them one at a time: O(n log n) total, since each of the n inserts costs O(log n).

The heap is the only structure of the three that keeps both insert and extract cheap at the same time — that balance, not raw speed on a single operation, is exactly why it is the standard choice whenever a system needs to repeatedly add new items and repeatedly pull out the current best one, hospital triage systems and Dijkstra's algorithm alike.

Active recall

1. Trace inserting 4, 10, 3, 18, 6 (in that order) into an empty max-heap, one value at a time, showing the array and any bubble-up swaps after each insertion. What is the final array?
2. Is the array [30, 20, 25, 10, 28, 8] a valid max-heap? Check the heap-order property at every parent node and justify your answer.
3. Given the max-heap [50, 40, 45, 20, 35, 42, 44], what value is returned by one call to extract-max, and what is the resulting array after the sift-down finishes?
4. Explain why extracting the maximum from an unsorted array costs O(n) but extracting the maximum from a max-heap costs only O(log n). What does the heap give up in exchange for this speed?
5. A classmate says: "Peek should be O(log n), because the computer has to walk down the tree to check that the root really is the biggest value." Is this correct? What is the true time complexity of peek, and why?

Answer key

1. Insert 4 → [4]. Insert 10 → append: [4,10]; parent(1)=0 holds 4; 10>4, swap → [10,4]. Insert 3 → append: [10,4,3]; parent(2)=0 holds 10; 3>10 is false, stop → [10,4,3]. Insert 18 → append: [10,4,3,18]; parent(3)=1 holds 4; 18>4, swap → [10,18,3,4]; now 18 is at index 1, parent(1)=0 holds 10; 18>10, swap → [18,10,3,4]; at the root, stop. Insert 6 → append: [18,10,3,4,6]; parent(4)=(4-1)//2=1 holds 10; 6>10 is false, stop. Final array: [18, 10, 3, 4, 6].
2. No, it is not a valid max-heap. Check every parent: index 0 (30) has children index 1 (20) and index 2 (25) — 30 ≥ 20 and 30 ≥ 25, fine. Index 1 (20) has children index 3 (10) and index 4 (28) — 20 ≥ 10 holds, but 20 ≥ 28 is false. This single violation (a child larger than its parent) is enough to break the heap property, regardless of what happens elsewhere in the array.
3. The root, 50, is returned. The last element (44) moves into the root slot and the array shrinks: [44,40,45,20,35,42]. Sift down from index 0 (44): children are index 1 (40) and index 2 (45); the larger child is 45, and 45 > 44, so swap → [45,40,44,20,35,42]. Now 44 is at index 2; its only child is index 5 (42) — index 6 doesn't exist in a 6-element array; 42 > 44 is false, so it stops. Returned value: 50. Resulting array: [45, 40, 44, 20, 35, 42].
4. An unsorted array gives no structural guarantee about where the maximum sits, so finding it requires inspecting every one of the n elements — a full linear scan. A heap enforces a standing invariant (every parent ≥ its children) that guarantees the maximum is always sitting at index 0, so finding it costs nothing extra, and after removing it, only the single root-to-leaf path needs fixing via sift-down — a path of length at most log₂(n), not the whole array. In exchange for this speed, a heap gives up total ordering: you cannot read off the 2nd or 3rd largest value directly, and you cannot binary-search a heap's array for an arbitrary value the way you could with a fully sorted array.
5. The classmate is incorrect. Peek is O(1), not O(log n). The reason no walk is needed is that the heap-order property is an invariant that insert and extract-max already maintain continuously, every time the structure changes — it is never left in a temporarily-broken state for peek to have to re-verify. Because the invariant guarantees the maximum is always at index 0 at every moment in time, peek can simply return data[0] directly, with no traversal or checking required.

Think About It

Think about this: How would you explain heaps and priority queues: always know the best to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind heaps and priority queues: always know the best, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.