Heap

Imagine you are running a hospital emergency room. Patients keep arriving, and at any moment you need to instantly know who needs help the most urgently, treat them, then instantly find the next most urgent patient. You do not have time to sort the entire waiting room every time someone new walks in. This exact problem, “always give me the smallest or biggest thing right now, and let me keep adding more things,” is what a heap is built to solve.

Note

This guide assumes you already know what a tree, a binary tree, and a complete binary tree are. If any of those feel shaky, it is worth checking out the Tree guide first, since heaps are built directly on top of that idea.

What Even Is a Heap?

A heap is a complete binary tree with one extra rule layered on top: every parent must follow a specific ordering compared to its children.

There are two flavors of heap, and they only differ in which direction that ordering rule points:

• Min Heap - every parent is smaller than or equal to its children, so the smallest value in the whole structure always sits at the root
• Max Heap - every parent is bigger than or equal to its children, so the largest value always sits at the root

Min Heap                  Max Heap
      1                        50
    /   \                    /    \
   3     5                 30      40
  / \   /                 /  \    /
 4   8 6                10   5  20

Caution

Here is a mistake almost every beginner makes at some point: a heap is not the same as a fully sorted list. Look at the min heap above. Its array form is [1, 3, 5, 4, 8, 6]. That is clearly not sorted, since 5 comes before 4. All a heap promises is that every parent is smaller (or bigger) than its own children. It says nothing about how two children compare to each other, or how nodes on opposite sides of the tree compare.

Why Bother Storing It as an Array?

Since a heap is always a complete binary tree (no gaps, filled left to right), you never need pointers to keep track of children. You can just lay every node out in a plain array, one after another, in level order, and use simple math to find anyone’s parent or children.

If a node sits at index i (using 0-based indexing), here is how you find its family:

Left child  = 2*i + 1
Right child = 2*i + 2
Parent      = (i - 1) // 2

Let us check this works using the min heap from above:

Tree:
            1
          /   \
         3     5
        / \   /
       4   8  6

Array:
Index:  0  1  2  3  4  5
Value: [1, 3, 5, 4, 8, 6]

Take index 1 (the value 3). Plugging into the formulas:

Left  = 2*1 + 1 = 3  -> arr[3] = 4
Right = 2*1 + 2 = 4  -> arr[4] = 8

And sure enough, 3 <= 4 and 3 <= 8, so the heap rule holds at that node.

This array trick is a big reason heaps are so fast and memory-friendly in practice: no extra pointers, no scattered memory, just one tidy array.

Min Heap vs Max Heap at a Glance

What you’re comparing	Min Heap	Max Heap
Element at the root	Smallest	Largest
Ordering rule	Parent <= children	Parent >= children
Common use	Priority queue (grab smallest first)	Priority queue (grab biggest first)
Used for sorting	Gives ascending order	Gives descending order

A simple way to remember this: think of a heap as a hierarchy of “power,” not a full ranking.

• In a Min Heap, the weakest one ends up on top
• In a Max Heap, the strongest one ends up on top

It only cares about parent versus child, never about comparing two cousins or far-apart relatives.

Where Heaps Actually Get Used

Min Heap shows up in:

• Priority queues where “smallest first” matters
• Dijkstra’s shortest path algorithm
• Finding the k smallest elements in a collection
• Merging several sorted lists together

Max Heap shows up in:

• Finding the k largest elements in a collection
• Task scheduling, where higher-priority tasks should run first
• Heap sort
• Counting frequencies (like “find the most common word”)

Adding a New Value: Insertion

Let us walk through inserting a new value into a min heap, step by step.

Rule Number One: New Values Always Go to the End

You can never just drop a new value wherever you feel like. To keep the tree “complete” (no gaps), every new value must be placed at the very next open spot, which is simply the end of the array.

Say we start with this valid min heap:

                     10
                  /       \
               20            30
             /    \         /    \
           40      50     60      70
          /  \     /
        80   90  100

Index:  0   1   2   3   4   5   6   7   8    9
Value: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

Now we want to insert 5. It goes straight to the end, at index 10:

                     10
                  /       \
               20            30
             /    \         /    \
           40      50     60      70
          /  \     / \
        80   90  100  5   <- new value

Rule Number Two: Bubble It Up Until It Fits

Placing it at the end almost always breaks the heap rule, since the new value has no idea if it belongs there. So we compare it against its parent, and if the parent is bigger (in a min heap), we swap them. We keep doing this, climbing upward, until either the rule is satisfied or we reach the root.

This climbing process is usually called bubbling up or percolating up.

1. Compare 5 with its parent, 50. Since 50 > 5, swap them.

2. Compare 5 with its new parent, 20. Since 20 > 5, swap them.

3. Compare 5 with its new parent, 10. Since 10 > 5, swap them.

4. 5 is now at the root. The root has no parent, so we stop here.

Here is the heap after all that bubbling:

                     5
                  /       \
               10            30
             /    \         /    \
           40      20     60      70
          /  \     / \
        80   90  100  50

Index:  0  1   2   3   4   5   6   7   8    9   10
Value: [5, 10, 30, 40, 20, 60, 70, 80, 90, 100, 50]

Let us double check every parent is smaller than its children: 5 < 10, 30, then 10 < 40, 20, then 30 < 60, 70, then 40 < 80, 90, then 20 < 100, 50. Everything checks out.

How Fast Is Insertion?

The number of swaps you might need is, at most, equal to the height of the tree, since bubbling up only ever travels straight up one path from a leaf to the root, never sideways.

Best case:    O(1)   (the new value is already in the right spot, zero swaps needed)
Worst case:   O(log N)   (the new value has to bubble all the way to the root)

Since a complete binary tree’s height is always around log2(N), insertion can never take longer than that.

Tip

A fun trick question: if you have N * 2^N total elements, what is the insertion time complexity? It is tempting to panic at the exponent, but remember, insertion time depends on the height of the tree, which is the logarithm of the total element count.

log(N * 2^N) = log(N) + log(2^N) = log(N) + N

Since N grows much faster than log(N), the dominant term is just N. So the answer is O(N). The lesson here: Big-O always depends on how many elements you actually have, not on how the count was described to you.

Removing the Top Value: Deletion

Deletion in a heap is intentionally limited, and that limitation is exactly what makes heaps useful.

Note

Deletion in a heap always happens at the root. You never get to pick and remove some random node in the middle. In a min heap, that means deletion always removes the smallest element. In a max heap, it always removes the largest.

Walking Through a Deletion

Let us use this min heap:

                     10
                  /       \
               20            30
             /    \         /    \
           40      50     60      70
          /  \    /  \
        80   90  100  110

Index:  0   1   2   3   4   5   6   7   8    9   10
Value: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110]

1. Remove the root. The root is 10, and that is what gets returned as the “deleted” value.

2. Move the very last element into the now-empty root spot. The last element here is 110, so it takes the root’s place. This keeps the tree complete, since we are filling the gap at the top using the node that was at the very end anyway.

                        110   <- moved here
                     /       \
                  20            30
                /    \         /    \
              40      50     60      70
             /  \     /
           80   90  100

3. Fix the broken heap rule. Right now 110 sits above 20 and 30, which breaks the min heap rule. So we compare 110 against its two children and swap with whichever child is smaller, repeating this all the way down until things settle. This downward fixing process is called heapify down or sift down.

Heapify Down, Step by Step

Compare 110 with 20 and 30. Smaller child = 20. Swap.

                     20
                  /       \
               110           30
             /    \         /    \
           40      50     60      70
          /  \     /
        80   90  100

Compare 110 with 40 and 50. Smaller child = 40. Swap.

                     20
                  /       \
               40            30
             /    \         /    \
           110     50     60      70
          /  \     /
        80   90  100

Compare 110 with 80 and 90. Smaller child = 80. Swap.

                     20
                  /       \
               40            30
             /    \         /    \
           80      50     60      70
          /  \     /
        110  90  100

110 is now sitting in a spot with no children at all, so we stop here.

Final Result After One Deletion

                     20
                  /       \
               40            30
             /    \         /    \
           80      50     60      70
          /  \
        110  90

Index:  0   1   2   3   4   5   6   7    8
Value: [20, 40, 30, 80, 50, 60, 70, 110, 90]

A Neat Pattern: Repeated Deletion Gives You Sorted Order

Here is something worth noticing: if you delete from a min heap once, you get the smallest value. Delete again, and you get the second smallest. Keep going, and you end up pulling values out in fully sorted, increasing order. This exact idea is what powers heap sort, which we will cover shortly.

How Fast Is Deletion?

Comparisons per level: 2 (checking both children)
Number of levels we might travel: log N

Total comparisons = roughly 2 * log N
Total swaps = at most 1 per level = log N

Overall deletion time = O(log N)

Building a Heap From Scratch

So far we have looked at inserting values one at a time into an already-valid heap. But what if someone hands you a big pile of unsorted numbers all at once, and you need to turn the whole thing into a heap? Inserting them one by one would work, but there is a much smarter way.

The Starting Point

Say we are given these numbers, in this exact order:

75, 25, 35, 45, 90, 80, 60, 20, 30, 77, 88

First, we just lay them out as a complete binary tree, exactly as given, with no comparisons or sorting yet.

                     75
                  /       \
               25            35
             /    \         /    \
           45      90     80      60
          /  \     / \
        20   30  77  88

Index:  0   1   2   3   4   5   6   7   8   9   10
Value: [75, 25, 35, 45, 90, 80, 60, 20, 30, 77, 88]

This is a valid complete binary tree, but it is definitely not a valid min heap yet. For example, 75 sits above 25, which breaks the rule immediately.

The Big Insight: Start From the Bottom, Not the Top

Here is the trick that makes this efficient: leaf nodes can never break the heap rule, since they have no children to compare against. So there is zero point in even looking at them. Instead, we start fixing things from the lowest non-leaf node, and work our way upward to the root.

To find where to start, use this formula:

last non-leaf index = (n // 2) - 1

With n = 11 elements:

last non-leaf index = (11 // 2) - 1 = 4

So we begin heapifying at index 4, then move to index 3, then 2, then 1, then finally 0 (the root).

Fixing Each Subtree, One at a Time

Index 4, the subtree (90, 77, 88): smallest is 77, so swap with 90.

      77
     /  \
   90   88

Index 3, the subtree (45, 20, 30): smallest is 20, so swap with 45.

      20
     /  \
   45   30

Index 2, the subtree (35, 80, 60): already follows the rule, nothing to do here.

      35
     /  \
   80   60

Index 1, the subtree (25, 20, 77): smallest is 20, swap, then keep checking downward since 25 moved into a new spot.

Step A: swap 25 and 20
      20
     /  \
   25   77

Step B: check 25 against its new children (45, 30). Already fine, stop.

Index 0, the root 75: this one needs the most work, since it has the furthest to travel.

Step A: compare 75 with 20 and 35. Swap with 20.
        20
       /  \
     75    35

Step B: compare 75 with its new children, 25 and 77. Swap with 25.
        25
       /  \
     75    77

Step C: compare 75 with its new children, 45 and 30. Swap with 30.
        30
       /  \
     45    75

The Final Heap

                     20
                  /       \
               25            35
             /    \         /    \
           30      77     80      60
          /  \     / \
        45   75  90  88

Index:  0   1   2   3   4   5   6   7   8   9   10
Value: [20, 25, 35, 30, 77, 80, 60, 45, 75, 90, 88]

Quick sanity check: 20 < 25, 35, then 25 < 30, 77, then 35 < 80, 60, then 30 < 45, 75, then 77 < 90, 88. All good, this is now a valid min heap.

Why This Method Is Surprisingly Fast

You might assume that doing N heapify operations, each costing up to O(log N), would multiply out to O(N log N) total. That feels logical, but it turns out to be the wrong estimate, and here is the intuition for why.

• Most nodes in a tree are leaves or close to leaves, and those barely move at all. Roughly half of all nodes need zero swaps.
• Only a tiny number of nodes (just the ones near the root) ever need to travel the full height of the tree.
• So the heavy, expensive work only happens for a small handful of nodes, while the bulk of the work is cheap or free.

This uneven distribution, lots of cheap work and very little expensive work, is exactly why the total adds up to a surprisingly small number.

Proving It Mathematically (For the Curious)

If you want the rigorous version: imagine grouping nodes by level, counting how many nodes are at each level and how many swaps each one might need in the worst case.

Level near the leaves:    about N/2 nodes,    each needs at most 0 swaps
One level above that:     about N/4 nodes,    each needs at most 1 swap
One level above that:     about N/8 nodes,    each needs at most 2 swaps
...continuing up to the root...
The root itself:          1 node,             needs at most log(N) swaps

Adding up “number of nodes at that level” times “max swaps at that level” across every level gives you a sum that looks like this:

Total swaps ≈ N * (1/2 + 2/4 + 3/8 + 4/16 + ...)

That series inside the parentheses is a well known one in math, and it converges to a constant value (it gets closer and closer to 2, no matter how many terms you add). Multiplying a constant by N gives you:

Total swaps = O(N)

Tip

You do not need to memorize the proof to use this fact in an interview. The one-sentence version that matters is: lower levels have tons of nodes but need almost no work, while upper levels need more work but have very few nodes, and that trade-off balances out to linear time overall, not N log N.

So, to summarize this section clearly:

Heap creation from scratch = O(N)

NOT O(log N)      <- this is the time for a single insert/delete, not building the whole thing
NOT O(N log N)    <- this is what you'd get if every node needed the full height of swaps, which is not the case

Heap Sort

Now that you understand insertion, deletion, and building a heap, heap sort is just putting all three ideas together.

The One-Line Idea

Build a heap, then keep removing the top element and placing it into its correct spot in the array, over and over, until nothing is left.

Why It Actually Sorts Things

Remember how repeated deletion from a min heap gives you values in increasing order? Heap sort leans on that exact same idea, just using a max heap so it can sort things in place without needing a second array.

Step 1: Build a max heap                    -> costs O(N)
Step 2: Remove the root N times              -> each removal costs O(log N)

Total time = O(N) + N * O(log N) = O(N log N)

Walking Through an Example

Starting array:

[4, 10, 3, 5, 1]

After turning it into a max heap:

[10, 5, 3, 4, 1]

Now we repeatedly take the biggest element (which is always at the front) and swap it to the end of the “active” portion of the array, then re-fix the heap for the smaller remaining portion:

After first extraction:  [1, 5, 3, 4, 10]
...continue extracting...
Final sorted array:      [1, 3, 4, 5, 10]

Writing Heap Sort From Scratch

Step 1: A heapify helper that fixes one subtree (max heap version)

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

Step 2: Build the max heap using the bottom-up trick from earlier

def build_max_heap(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

Step 3: Repeatedly pull out the maximum and shrink the heap

def heap_sort(arr):
    n = len(arr)

    build_max_heap(arr)

    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]   # move current max to its final spot
        heapify(arr, i, 0)                 # fix the heap for the smaller remaining part

Trying it out

arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print(arr)
# Output: [1, 3, 4, 5, 10]

How Fast and How Much Memory Does It Use?

Case	Time
Best	O(N log N)
Average	O(N log N)
Worst	O(N log N)

This consistency (it never has a bad worst case, unlike quick sort) is one of heap sort’s biggest selling points.

Space-wise, this manual version sorts in place, using just O(1) extra memory.

Is Heap Sort Stable?

No. Stability means that if two elements are equal, they keep their original relative order after sorting. Heap sort does not promise that, since swaps during heapify can shuffle equal elements past each other. If you ever need stability (say, sorting people by age while keeping same-age people in their original order), heap sort is not the right tool.

Heap Sort Compared to Other Sorts

Algorithm	Worst Case	Stable	Extra Space
Heap Sort	O(N log N)	No	O(1)
Quick Sort	O(N^2)	No	O(log N)
Merge Sort	O(N log N)	Yes	O(N)

Reach for heap sort when:

• You absolutely need a guaranteed O(N log N) worst case (quick sort can degrade to O(N^2) in unlucky cases)
• You are tight on memory and need in-place sorting

Avoid heap sort when:

• You need stable sorting
• Cache performance matters a lot (heap sort jumps around memory more than something like merge sort)

Heap Sort Using Python’s heapq (The Easy Way)

Python’s built-in heapq module only gives you a min heap directly, so there are two common approaches.

Approach 1: Plain min heap (gives ascending order, but uses extra memory)

import heapq

def heap_sort_min(arr):
    heapq.heapify(arr)
    result = []
    while arr:
        result.append(heapq.heappop(arr))
    return result

nums = [4, 10, 3, 5, 1]
print(heap_sort_min(nums))
# Output: [1, 3, 4, 5, 10]

This costs O(N log N) in time, but unlike the manual version, it needs O(N) extra space for the result list, so it is not in-place.

Approach 2: Faking a max heap using negative numbers

Since heapq only understands “smallest first,” a classic trick is to flip the sign of every number going in, then flip it back when reading values out. Negating numbers reverses their order, so the “smallest” negative number corresponds to the “largest” original number.

import heapq

def heap_sort_max(arr):
    max_heap = [-x for x in arr]
    heapq.heapify(max_heap)

    result = []
    while max_heap:
        result.append(-heapq.heappop(max_heap))
    return result

nums = [4, 10, 3, 5, 1]
print(heap_sort_max(nums))
# Output: [10, 5, 4, 3, 1]

	Manual Heap Sort	Using heapq
In place	Yes	No
Extra space	O(1)	O(N)
Time	O(N log N)	O(N log N)
Good for interviews	Yes, shows you understand internals	Usually not what’s expected
Good for real projects	More code to maintain	Quick and convenient

Python’s heapq Module, Properly Explained

If you are writing Python day to day, you will almost never write your own heap from scratch, you will just import heapq. Here is what each piece actually does.

A quick refresher on what heapq assumes by default: it is array-based, and it defaults to min heap behavior, meaning the smallest element always sits at index 0.

Turning a List Into a Heap: heapify

heapq.heapify(arr)

This rearranges a normal list into valid min heap order, in place. It does not fully sort the list, it only guarantees that arr[0] is the smallest element. Just like the “building a heap” section above, this runs in O(N) time, not O(N log N), thanks to that same bottom-up insight.

arr = [12, 13, 79, 90, 23, 89, 34, 14, -2, -9, 6]
heapq.heapify(arr)
print(arr)
# Some valid heap order, NOT fully sorted, something like:
# [-9, -2, 6, 14, 12, 79, 34, 90, 13, 23, 89]

Adding One Value: heappush

heapq.heappush(arr, 8)

This appends the new value at the end, then bubbles it up until the heap rule holds again, exactly like the manual insertion process we walked through earlier. Time complexity: O(log N).

Removing the Smallest Value: heappop

smallest = heapq.heappop(arr)

This removes and returns the smallest value (the root), moves the last element into its place, and sifts it down until the heap rule is restored again. This matches the manual deletion process step for step. Time complexity: O(log N).

Just Looking, Without Removing: Peek

smallest_without_removing = arr[0]

Since the smallest value always sits at index 0, you do not need any special function to peek at it. No restructuring needed at all, so this is O(1).

Push and Pop in One Smooth Move: heappushpop

result = heapq.heappushpop(arr, 6)

This pushes a new value in, then immediately pops and returns the smallest value, all done as a single optimized operation. It behaves the same as calling heappush followed by heappop separately, but is faster because it avoids redundant work. This pattern is especially handy when you need to keep a heap at a fixed size, like solving “streaming top-k” style problems. Time complexity: O(log N).

Pop Then Push: heapreplace

result = heapq.heapreplace(arr, 8)

This is the mirror image of heappushpop. Instead of pushing first, it pops the smallest value first, and then pushes the new one in. It assumes the heap is not already empty when you call it.

Function	Order of operations
heappushpop	push, then pop
heapreplace	pop, then push

Time complexity: O(log N).

Finding the K Smallest or K Largest Values

heapq.nsmallest(k, arr)
heapq.nlargest(k, arr)

These work on any iterable, not just things that are already heaps. Under the hood, nsmallest actually builds a small max heap of size k as it scans through everything, only keeping the smallest k values it has seen so far. nlargest does the mirror version using a small min heap of size k.

Time complexity: O(N log k)

Why does this beat just sorting everything? Sorting the whole list costs O(N log N). When k is much smaller than N, O(N log k) is noticeably faster, since you only ever need to manage a heap of size k, not the entire dataset.

Faking a Max Heap With Negative Numbers (The Classic Trick)

For a long time, heapq had no built-in max heap option at all, so this negation trick became the standard workaround, and it is still extremely common to see in interviews and real code.

max_heap = []
for x in arr:
    heapq.heappush(max_heap, -x)

largest = -heapq.heappop(max_heap)

The logic: negating every number flips the comparison order completely, so “the smallest negative number” is exactly the same thing as “the largest original number.” Push and pop work exactly as before, you just remember to flip the sign on the way in and on the way back out.

Why people still use this trick:

• It works on every version of Python, with no compatibility worries

Why it is a little annoying:

• It is less readable at a glance
• You have to remember to negate consistently everywhere you touch the heap

Newer Max Heap Functions

Some newer Python versions have started adding dedicated max heap functions directly: heapify_max, heappush_max, heappop_max, heappushpop_max, and heapreplace_max. They work exactly like their min heap counterparts, just with the comparison direction flipped, so the largest element ends up at the root instead of the smallest.

Caution

These functions are quite new and were not officially documented or stabilized for a long time after being added. If you are working on something that needs to run reliably across many environments, or if you are in an interview setting, it is safer to stick with the well established negative-number trick, and just mention that dedicated max heap functions exist in newer Python versions if it comes up.

Quick Reference Table for heapq

What you want to do	Function	Time
Turn a list into a min heap	heapify	O(N)
Add one value	heappush	O(log N)
Remove the smallest	heappop	O(log N)
Just look at the smallest	arr[0]	O(1)
Push then pop	heappushpop	O(log N)
Pop then push	heapreplace	O(log N)
Get k smallest values	nsmallest	O(N log k)
Get k largest values	nlargest	O(N log k)

Common Mistakes to Watch Out For

• Thinking a heap is fully sorted. It only guarantees parent versus child ordering, nothing about siblings or cousins.
• Saying heap creation is O(log N) or O(N log N). It is actually O(N), thanks to most nodes needing very few or zero swaps.
• Forgetting that heapify() rearranges in place but does not return a sorted list. Only arr[0] is guaranteed to be correct after calling it.
• Calling heapq operations “in-place” sorting when extra lists are involved. Approaches that build a separate result list use O(N) extra space, not O(1).
• Assuming heap sort is stable. It is not, equal elements can get reordered.
• Trying to delete an arbitrary node from the middle of a heap. Standard heap deletion only ever removes the root.

Quick Reference

Heap

A complete binary tree where every parent follows an ordering rule compared to its children. Min heap keeps the smallest on top, max heap keeps the largest on top.

Insertion

New values go to the end of the array, then bubble up by swapping with the parent until the rule holds. Costs O(log N) in the worst case.

Deletion

Always removes the root. The last element takes its place, then sifts down by swapping with the smaller (or bigger) child until the rule holds again. Costs O(log N).

Building a Heap

Start from the last non-leaf node and heapify upward to the root. Leaf nodes need zero work, so the total cost is O(N), not O(N log N).

Heap Sort

Build a heap in O(N), then repeatedly remove the root and shrink the heap. Total cost O(N log N), in-place, but not stable.

Python heapq

A ready-made min heap toolkit. Use heapify, heappush, and heappop for the basics, and the negative-number trick for a max heap.

Summary

The Core Idea

• A heap is a complete binary tree with an ordering rule between every parent and its children
• Min heap keeps the smallest value at the root, max heap keeps the largest value at the root
• A heap is not fully sorted, it only guarantees parent versus child order
• Heaps are stored as plain arrays using simple index math for parent and child relationships

Classic Operations

• Insertion - add to the end, then bubble up, O(log N) worst case
• Deletion - remove the root, move the last element up, then sift down, O(log N)
• Building a heap from scratch - heapify bottom-up from the last non-leaf node, O(N) total
• Heap sort - build a heap, then repeatedly extract the root, O(N log N) overall

Interview Tips

• Always state clearly: heap creation is O(N), not O(N log N)
• Remember deletion only ever happens at the root, never at an arbitrary node
• Know that heap sort is not stable, unlike merge sort
• For max heap behavior with Python’s heapq, default to the negative-number trick
• nsmallest and nlargest run in O(N log k), which beats full sorting when k is much smaller than N
• Be ready to explain why heap creation is linear: most nodes are near the leaves and need almost no work