Heap Sort

Quicksort’s average case is excellent, but its worst case is a real $O(n^2)$. Heap sort trades a little bit of that average-case speed for a guarantee: $O(n \log n)$ in the best, average, and worst case — every time, no randomization required. It reuses exactly the binary-heap machinery from Phase 3, just aimed at a full array instead of a live priority queue.

What you’ll learn

• Heapify (sift-down) applied bottom-up to build a max-heap from a raw array, in $O(n)$.
• The extraction loop: repeatedly swap the max to the end, shrink the heap, and sift down — sorting the array in place.
• Why heap sort’s worst case is always $O(n \log n)$, with $O(1)$ extra space.
• Why heap sort is not stable (unlike merge sort).
• How this compares to just using heapq directly.

The cue

Heap sort itself is almost never the ask. The sift-down and the linear-time build are.

You are looking at heap machinery when…

• The problem wants the k largest / smallest / most frequent and k is much smaller than n — a bounded heap, Top K.
• Items arrive as a stream and you must always know the current extreme, with $O(1)$ space per tracked item beyond the heap.
• You need repeated extract-min while inserting — Dijkstra, task scheduling, merging k runs.
• The interviewer asks for guaranteed $O(n \log n)$ with $O(1)$ extra space. That is heap sort, and it is the only common sort that gives both.
• Someone asks “why is building a heap $O(n)$ and not $O(n \log n)$?” — a favourite because the obvious answer is wrong.

When it is the wrong tool. Heap sort is $O(n \log n)$ guaranteed but has poor cache locality and loses badly to Timsort on real data — so in Python you use list.sort(). It is also not stable. If you want the sorted order and stability, that is merge sort. If you only want one extreme, min/max is $O(n)$ with no structure at all.

Step 1: build a max-heap, in place

Recall from Phase 3 that a max-heap array obeys one invariant: every parent is $\ge$ both its children. heapify(arr, n, i) fixes that invariant at index i, assuming both its subtrees are already valid heaps — it sifts the value at i down until it lands in the right spot.

heapify.py

def heapify(arr, n, i):
    """Sift arr[i] down so the subtree rooted at i is a valid max-heap.
    Assumes the left and right subtrees of i are already max-heaps."""
    largest = i
    left, right = 2 * i + 1, 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)   # keep sifting down the swapped subtree
 
 
arr = [4, 10, 3, 5, 1]
heapify(arr, len(arr), 0)
print("after heapify at root:", arr)

To turn a whole array into a max-heap, call heapify on every internal node (any index with at least one child), starting from the last internal node and working back to the root. Leaves are already trivially valid one-element heaps, so they’re skipped.

build_max_heap.py

def heapify(arr, n, i):
    largest = i
    left, right = 2 * i + 1, 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)
 
 
def build_max_heap(arr):
    n = len(arr)
    last_internal_node = n // 2 - 1
    for i in range(last_internal_node, -1, -1):
        heapify(arr, n, i)
    return arr
 
 
arr = [4, 10, 3, 5, 1, 6, 8]
print("raw array:      ", arr)
print("built max-heap: ", build_max_heap(arr))

Why this is O(n), not O(n log n)

Calling heapify once per node costs at most $O(\log n)$ each, and there are $n$ nodes, suggesting $O(n \log n)$ — but most nodes sit near the bottom of the tree, where a sift-down has almost no distance to travel. Summed across all levels, the total work collapses to $O(n)$. This is the same amortized result heapq.heapify relies on.

Step 2: repeatedly extract the max

The array’s root (arr[0]) is now the maximum. Swap it with the last element of the current heap, shrink the heap by one (the last slot is now permanently correct — part of the sorted suffix), and sift the new root down to restore the heap. Repeat until only one element is left.

heap_sort.py

def heapify(arr, n, i):
    largest = i
    left, right = 2 * i + 1, 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)
 
 
def heap_sort(arr):
    n = len(arr)
 
    # Phase 1: build a max-heap, O(n)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
 
    # Phase 2: repeatedly extract the max into the sorted suffix, O(n log n)
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]   # move current max to the end
        heapify(arr, end, 0)                   # heap_size shrinks to `end`
 
    return arr
 
 
nums = [4, 10, 3, 5, 1, 6, 8, 2]
print("sorted:", heap_sort(nums))

Both phases work on the same array — no auxiliary buffer is ever allocated, which is why heap sort’s extra space is $O(1)$ (ignoring the recursion stack, which is $O(\log n)$, or $O(1)$ if heapify is written iteratively).

Watch one extract-and-sift-down cycle

sketch Heap sort: extract max, sift down p5.js Pause Restart

The root (always the current max) swaps with the last element of the shrinking heap, which locks it into the sorted suffix (green). Sift-down then restores the max-heap invariant on what's left.

Contrast with heapq

Python’s heapq module is always a min-heap and works by mutating a list through repeated heappush/heappop calls — it’s built for a live priority queue, not specifically for sorting an existing array in place.

heapq_vs_heap_sort.py

import heapq
 
 
def heap_sort(arr):
    n = len(arr)
 
    def heapify(a, size, i):
        largest = i
        left, right = 2 * i + 1, 2 * i + 2
        if left < size and a[left] > a[largest]:
            largest = left
        if right < size and a[right] > a[largest]:
            largest = right
        if largest != i:
            a[i], a[largest] = a[largest], a[i]
            heapify(a, size, largest)
 
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        heapify(arr, end, 0)
    return arr
 
 
data = [4, 10, 3, 5, 1, 6, 8, 2]
 
# Classic heap sort: builds a MAX-heap, sorts the SAME array in place
in_place_result = heap_sort(list(data))
 
# heapq way: builds a MIN-heap, then pops smallest-first into a NEW list
h = list(data)
heapq.heapify(h)                              # O(n), in place
via_heapq = [heapq.heappop(h) for _ in h]     # O(n log n), builds a new list
 
print("classic heap sort (in place): ", in_place_result)
print("heapq.heapify + pops (new list):", via_heapq)

Both give the same ascending order and the same $O(n \log n)$ total time — the difference is that classic heap sort keeps everything inside one array with $O(1)$ extra space, while collecting heapq pops into a fresh list uses $O(n)$ extra space (though heapq.heapify itself is in place). In practice: reach for heapq when you need a live priority queue (items pushed/popped over time); reach for sorted() / .sort() (Timsort, next lesson) when you just need to sort a finished array — hand-rolled heap sort is mostly an interview/CS-fundamentals topic today.

Dry run

heapsort([4, 10, 3, 5, 1])

Phase 1 — build the max-heap, sifting down from the last internal node backwards:

Sift from index	Value	Array after
1	10	[4, 10, 3, 5, 1] — already correct, no swap
0	4	[10, 5, 3, 4, 1]

Note the loop starts at n // 2 - 1 = 1, not at the end. Leaves need no sifting — they have no children to violate the heap property — and roughly half of all nodes are leaves. That single observation is where the linear-time bound comes from.

Phase 2 — repeatedly swap the root to the end and re-sift:

Step	Array after	Sorted tail
swap root to index 4	[5, 4, 3, 1, 10]	[10]
swap root to index 3	[4, 1, 3, 5, 10]	[5, 10]
swap root to index 2	[3, 1, 4, 5, 10]	[4, 5, 10]
swap root to index 1	[1, 3, 4, 5, 10]	[3, 4, 5, 10]

Result [1, 3, 4, 5, 10], ascending — from a max-heap. That inversion is the point: the largest element is at the root, and swapping it to the end of the array is what builds the sorted region backwards, in place, with no extra memory.

The heap shrinks by one each step (sift_down(a, 0, end) treats everything from end onward as frozen), so the array is simultaneously a shrinking heap and a growing sorted suffix. No second array is ever allocated.

Why build-heap is $O(n)$, measured

Counting the actual swaps performed during the build phase:

n	Ascending input	Random input (avg of 200)	$n \log_2 n$
15	11	7.7	45
31	26	18.6	124
63	57	41.4	315
127	120	88.3	762
255	247	182.5	1,785

The swap count tracks n, not $n \log n$ — at n = 255 it is 247, about 7x below the $n \log_2 n$ figure of 1,785, and the ratio widens as n grows.

The reason is the shape of the tree. A node at height h costs at most h swaps, and there are about $n/2^{h+1}$ nodes at that height — so the total is $\sum_h h \cdot n/2^{h+1} = n \sum_h h/2^{h+1}$, and that sum converges to 1. Half the nodes are leaves and cost nothing; only the single root can cost $\log n$. Sifting down from the bottom is what exploits this; inserting n elements one at a time and sifting up is genuinely $O(n \log n)$, because there the expensive nodes are the numerous ones.

The overall sort is still $O(n \log n)$ — phase 2 does n extractions of $O(\log n)$ each, and that is the dominant term. The linear build is a real result and it does not change the sort’s class.

Pitfalls

• Starting the build loop at n - 1 instead of n // 2 - 1. Correct but wasteful: leaves have no children, so sifting them is a no-op. Half the array is leaves.
• Building with n sift-ups instead of sift-downs from the bottom. That version is genuinely $O(n \log n)$, not $O(n)$ — and it is the one people accidentally describe when asked why the build is linear. Measured: sift-down build costs ~247 swaps at n = 255, against an $n \log_2 n$ budget of 1,785.
• Using a min-heap and expecting ascending output. A max-heap gives ascending order, because each extracted maximum is placed at the shrinking end of the array. A min-heap gives descending.
• Forgetting to shrink the heap boundary. sift_down(a, 0, end) must treat indices from end onward as frozen. Pass the full length and the sorted suffix gets pulled back into the heap.
• Off-by-one in the child indices. For a 0-indexed array the children of i are 2i + 1 and 2i + 2, and the parent is (i - 1) // 2. The 1-indexed formulas (2i, 2i + 1, i // 2) are what most textbooks print, and mixing conventions silently corrupts the heap.
• Not bounds-checking both children. if l < n and if r < n — a node can have exactly one child, and only the last internal node can.
• Assuming heap sort is stable. It is not: the root swap moves elements across the whole array. Merge sort is the stable $O(n \log n)$.
• Reaching for heap sort in Python for speed. list.sort() is Timsort in C and wins comfortably. Heap sort’s practical claim is guaranteed $O(n \log n)$ in $O(1)$ space — not wall-clock speed, where poor cache locality hurts it.
• Confusing heapq.heapify with this build. heapify is exactly the same $O(n)$ bottom-up build, but heapq is a min-heap only — negate the values to simulate a max-heap.

Time and space complexity

Case	Complexity	Why
Best	$O(n \log n)$	Build is $O(n)$; $n$ extractions at $O(\log n)$ each — no shortcut exists
Average	$O(n \log n)$	Same reasoning, no dependence on input order
Worst	$O(n \log n)$	Guaranteed — no adversarial input degrades it, unlike quicksort
Space	$O(1)$	Sorts in place; no auxiliary array (heap is the array)
Stable?	No	Swapping the root with the last element can reorder equal keys

Heap sort vs quicksort

Heap sort’s guaranteed $O(n \log n)$ worst case sounds strictly better than quicksort’s average-case-good-but-worst-case-$O(n^2)$ — but in practice, quicksort usually wins on wall-clock time because of better cache locality (it accesses nearby memory; heap sort jumps around the array via 2i+1/2i+2 index math) and a smaller constant factor. Heap sort’s selling point is the guarantee, which matters for real-time systems where a rare $O(n^2)$ spike is unacceptable.

The variant map

Variant	The change	Where it shows up
Ascending output	Max-heap; extract to the shrinking end	this page
Descending output	Min-heap, same structure	—
k largest without full sorting	Stop after k extractions: $O(n + k \log n)$	215
Bounded top-k over a stream	A size-k heap instead of an n-heap: $O(n \log k)$, $O(k)$ space	703 · 347
Priority queue	Keep the heap, drop the sorting — push and pop as needed	Dijkstra, task scheduling
Merge k sorted runs	Heap of one head per run	23 · 378
Running median	Two heaps, min and max	295
heapq.heapify	The identical $O(n)$ bottom-up build, min-heap only	stdlib
heapq.nlargest(k, …)	The bounded-heap pattern, in C	stdlib
d-ary heap	d children per node: shallower tree, cheaper decrease-key, costlier sift-down	Dijkstra tuning
Introsort’s fallback	Heap sort is what std::sort switches to when quicksort goes bad	C++

The stdlib is a min-heap; negate for a max-heap

heapq provides no max-heap. Push -value and negate on the way out, or push tuples with a negated key. heapq.heapify is exactly the $O(n)$ bottom-up build from this page — so “why is heapify linear?” and “why is build-heap linear?” are the same question, and both are answered by “cost tracks height, and most nodes are leaves”.

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 1985 — Find the Kth Largest Integer in the Array · Medium

Problem. nums is an array of strings representing integers without leading zeros. Return the kth largest as a string. Duplicates count separately.

Constraints. 1 <= k <= len(nums) <= 10^4, each string has up to 100 digits.

Examples. ["3","6","7","10"], k = 4 gives "3" · ["2","21","12","1"], k = 3 gives "2" · ["0","0"], k = 2 gives "0"

pch.exerciseTag pch.exerciseTitle

Editorial

The strings are the point. Sorting them lexicographically would put "10" before "2", which is wrong numerically. Since there are no leading zeros, a longer string is always a larger number, and equal-length strings compare correctly as text — so (len(s), s) is exactly numeric order.

Time $O(n \log k)$ with nlargest. Space $O(k)$.

["2","21","12","1"], k = 3 is the discriminating case: numeric order is 21, 12, 2, 1, so the third largest is "2". A plain lexicographic sort gives 21, 2, 12, 1 and answers "12".

In Python you could simply use key=int — integers are arbitrary-precision, so 100-digit values are fine. Worth mentioning, and the (len, s) key is the answer that survives in languages without big integers.

Follow-ups: ”$O(n)$ average?” — quickselect with the same comparison key. “Why not sorted(...)[-k]?” — $O(n \log n)$; fine here, but nlargest is $O(n \log k)$. “What if leading zeros were allowed?” — strip them first, or the length heuristic breaks.

LC 451 — Sort Characters By Frequency · Medium

Problem. Sort the characters of a string in decreasing order of frequency. Characters with the same frequency may appear in any order.

Constraints. 1 <= len(s) <= 5 * 10^5, letters and digits.

Examples. "tree" gives "eert" or "eetr" · "cccaaa" gives "cccaaa" or "aaaccc" · "Aabb" gives "bbAa" or "bbaA"

Why this test checks properties

Equal-frequency characters may be ordered arbitrarily, so the test verifies the multiset of characters is unchanged and that all occurrences of each character are grouped together — the two things any correct answer must satisfy.

pch.exerciseTag pch.exerciseTitle

Editorial

Count, then emit. Counter.most_common() returns pairs already sorted by decreasing count, so the whole solution is one comprehension.

Time $O(n + |\Sigma| \log |\Sigma|)$ — linear counting plus a sort over the distinct characters only. Space $O(n)$.

Two Python points worth making:

• join over a generator, not result += ch * n in a loop. Strings are immutable, so repeated concatenation is $O(n)$ per step and $O(n^2)$ overall. At len(s) = 5 * 10^5 that is the difference between passing and timing out.
• Bucket sort avoids the sort entirely: frequencies are bounded by len(s), so index a list of buckets by count and read it from the high end. That gives a true $O(n)$ — the same idea as LC 347, and the right answer if asked to beat $O(|\Sigma| \log |\Sigma|)$.

A max-heap of (-count, char) is a third valid route and the one that connects to this page, at $O(n + |\Sigma| \log |\Sigma|)$.

Follow-ups: “Truly $O(n)$?” — bucket by frequency. “Break ties alphabetically?” — key on (-count, char); that is LC 692’s shape. “Sort words by frequency?” — same counting, different tokens.

LC 692 — Top K Frequent Words · Medium

Problem. Return the k most frequent words, sorted by decreasing frequency and, for equal frequency, increasing lexicographic order.

Constraints. 1 <= len(words) <= 500, 1 <= len(words[i]) <= 10, lowercase, k is valid.

Examples. ["i","love","leetcode","i","love","coding"], k = 2 gives ["i","love"] · ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4 gives ["the","is","sunny","day"]

pch.exerciseTag pch.exerciseTitle

Editorial

The interesting part is the mixed directions: frequency descending, but words ascending on ties. Since strings cannot be negated, the trick is a tuple key with the sign flipped on the numeric field only: (-count, word).

Time $O(n + m \log k)$ for m distinct words. Space $O(m)$.

Note the use of nsmallest with a negated count rather than nlargest. With nlargest the word component would also reverse, giving descending alphabetical order on ties — wrong. That asymmetry is precisely why the mixed-direction case is worth practising; see Sorting with Custom Comparators.

The second example is the discriminating one: is and sunny both occur twice, and is must come first alphabetically.

An alternative that also works and is worth mentioning: two stable sorts — sort by word ascending, then by count descending. Python’s sort stability preserves the alphabetical order within equal counts.

Follow-ups: ”$O(n)$?” — bucket by frequency, then sort each bucket alphabetically. “Why not nlargest?” — it would reverse the tie-break too. “Top k frequent numbers (LC 347)?” — no tie-break specified, so it is easier.

Practice

Heap sort itself is rarely asked; the sift-down and the build-heap-in-linear-time argument behind it are. These problems all run on a heap, so they exercise the same mechanics with a real question attached.

9 problems

2 easy5 medium2 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○1046Last Stone WeighteasyNeetCode 150
• ○1051Height Checkereasy
• ○347Top K Frequent ElementsmediumNeetCode 150Blind 75amazonmetauberbytedance
• ○621Task SchedulermediumNeetCode 150metaamazonuber
• ○147Insertion Sort Listmedium
• ○215Kth Largest Element in an ArraymediumNeetCode 150LeetCode Top Interview 150
• ○912Sort an Arraymedium
• ○23Merge k Sorted ListshardNeetCode 150Blind 75LeetCode Top Interview 150
• ○1851Minimum Interval to Include Each QueryhardNeetCode 150

Self-check

pch.quizTag pch.quizDefaultTitle

1. The build phase loops from `n // 2 - 1` down to 0. Why not from `n - 1`?

   A To save a constant factor of two B Indices from n // 2 onward are leaves -- they have no children, so sifting them is a no-op, and about half of all nodes are leaves C Because the last element is already in place D Because sifting a leaf would raise an IndexError
   pch.quizShowAnswer

   B — Indices from n // 2 onward are leaves -- they have no children, so sifting them is a no-op, and about half of all nodes are leaves — It is not merely a constant saving -- the fact that half the nodes cost nothing is the foundation of the linear-time bound. A node at height h costs at most h swaps and there are about n/2^(h+1) such nodes, so the total sum converges to O(n). Sifting leaves would be harmless, just pointless.

2. Why is building a heap O(n) rather than O(n log n)?

   A Because each sift-down is O(1) B Cost is proportional to a node's height, and most nodes are near the bottom -- the sum of h * n/2^(h+1) converges to O(n) C Because the array is already partially sorted D It is O(n log n); the O(n) claim is a myth
   pch.quizShowAnswer

   B — Cost is proportional to a node's height, and most nodes are near the bottom -- the sum of h * n/2^(h+1) converges to O(n) — The many nodes are cheap and the expensive nodes are few -- only the root can cost log n. Measured swap counts track n rather than n log n: 247 at n = 255 against an n log2 n budget of 1,785, and the gap widens with n. Inserting n elements one at a time and sifting *up* inverts the shape and genuinely is O(n log n).

3. Heap sort builds a MAX-heap yet produces ascending output. How?

   A It reverses the array at the end B Each extracted maximum is swapped to the shrinking END of the array, so the sorted region grows backwards C It converts the max-heap to a min-heap after building D The output is actually descending
   pch.quizShowAnswer

   B — Each extracted maximum is swapped to the shrinking END of the array, so the sorted region grows backwards — Traced on [4,10,3,5,1]: after the build the array is [10,5,3,4,1], and the largest element goes to the last slot, then the next largest to the second-to-last, and so on -- final result [1,3,4,5,10]. Placing the maximum at the end is exactly what lets the sort be in place: the array is a shrinking heap and a growing sorted suffix at once.

4. In phase 2 you call `sift_down(a, 0, end)` rather than `sift_down(a, 0, len(a))`. Why does that matter?

   A It is a micro-optimisation B Everything from `end` onward is the finished sorted region -- pass the full length and those elements get pulled back into the heap C It avoids an IndexError on the last element D It keeps the heap balanced
   pch.quizShowAnswer

   B — Everything from `end` onward is the finished sorted region -- pass the full length and those elements get pulled back into the heap — The boundary is what separates the two roles the array is playing. Sift with the full length and the largest element -- just placed at the end -- looks like a heap member again, gets swapped back toward the root, and the sort silently produces garbage. Shrinking the boundary by one per extraction is the whole in-place trick.

5. For a 0-indexed array, what are the children and parent of index i?

   A Children 2i and 2i+1; parent i // 2 B Children 2i+1 and 2i+2; parent (i-1) // 2 C Children i+1 and i+2; parent i-1 D Children 2i+1 and 2i+2; parent i // 2
   pch.quizShowAnswer

   B — Children 2i+1 and 2i+2; parent (i-1) // 2 — The 2i / 2i+1 / i//2 formulas are the 1-indexed ones most textbooks print, and mixing conventions corrupts the heap without raising -- you get a plausible wrong order. Note also that both children need separate bounds checks: a node can have exactly one child, and only the last internal node can.

6. When would you actually choose heap sort in practice?

   A When you want the fastest possible sort B When you need a guaranteed O(n log n) with O(1) extra space and do not need stability C When the data is nearly sorted D When you need stable output
   pch.quizShowAnswer

   B — When you need a guaranteed O(n log n) with O(1) extra space and do not need stability — That combination is heap sort's unique selling point -- quicksort risks O(n^2), merge sort needs O(n) space. What it is not is fast in practice: poor cache locality means Timsort beats it comfortably, and nearly-sorted data is Timsort's best case and no help at all to a heap. It is also not stable, since the root swap moves elements across the whole array.

Recall card

• Two phases: build a max-heap in place, then repeatedly swap the root to the shrinking end and sift down.
• Build from n // 2 - 1 downwards. Indices from n // 2 on are leaves and need no sifting.
• Build is $O(n)$, not $O(n \log n)$. Cost tracks a node’s height, and most nodes are near the bottom: measured 247 swaps at n = 255 against an $n \log_2 n$ budget of 1,785. Sifting up n times instead really is $O(n \log n)$.
• The whole sort is still $O(n \log n)$ — n extractions at $O(\log n)$ dominate the linear build.
• A max-heap yields ascending output, because each extracted maximum lands at the end.
• Shrink the heap boundary each extraction (sift_down(a, 0, end)), or the sorted suffix gets pulled back in.
• 0-indexed: children 2i+1, 2i+2; parent (i-1)//2. Bounds-check both children separately.
• $O(1)$ extra space, $O(n \log n)$ guaranteed, and not stable. That trio is the entire reason to reach for it.
• In Python, use list.sort(). Heap sort’s cache locality is poor; heapq.heapify is this same linear build, min-heap only, so negate for a max-heap.

Interview follow-ups

They ask	What they’re checking	The answer
“Why is building a heap $O(n)$?”	The classic, and the obvious answer is wrong	Cost is a node’s height, not the tree’s depth, and most nodes sit near the bottom: $\sum_h h \cdot n/2^{h+1}$ converges to $O(n)$. Measured — 247 swaps at n = 255 against an $n \log_2 n$ budget of 1,785
“So is heap sort $O(n)$?”	Whether you conflate the phases	No. The build is $O(n)$; the n extractions at $O(\log n)$ each dominate, so the sort is $O(n \log n)$
“Why not build by inserting n times?”	The direction matters	Sifting up from the top puts the expensive work on the numerous nodes, giving a genuine $O(n \log n)$. Sifting down from the bottom is what earns the linear bound
“When would you pick heap sort?”	Its actual niche	Guaranteed $O(n \log n)$ and $O(1)$ extra space, when stability is not required. Quicksort risks $O(n^2)$; merge sort needs $O(n)$ space. Heap sort is the only common sort giving both
“Is it stable?”	Requirements	No — the root swap moves elements across the whole array. Merge sort is the stable $O(n \log n)$
“Then why is nothing written in heap sort?”	Practical honesty	Cache locality. Sift-down jumps by powers of two, so it misses cache constantly, while merge and Timsort walk memory sequentially. Same class, much worse constant
“Give me the k largest without sorting”	Choosing the right bound	Build in $O(n)$, then k extractions: $O(n + k \log n)$. If k \ll n and the data streams, a bounded size-k heap is better — $O(n \log k)$ and $O(k)$ space
“Max-heap in Python?”	heapq fluency	There isn’t one — negate on the way in and out, or push a tuple with a negated key. heapify is this page’s linear build
“What is the parent of index i?”	Index arithmetic under pressure	(i - 1) // 2 for a 0-indexed array; children 2i + 1 and 2i + 2. The 2i/i // 2 formulas are 1-indexed, and mixing conventions corrupts the heap without raising
“Could you sort in place with heapq?”	Knowing the library’s limits	Not directly — heapq is min-only, so you would negate everything, heapify, then heappop n times into a list. That is $O(n)$ extra space, which throws away heap sort’s one advantage; write the sift-down yourself

Recap

• Heap sort has two phases: build a max-heap in $O(n)$, then extract the max $n$ times, each extraction costing $O(\log n)$ for the sift-down.
• Extraction swaps the root with the current last heap element, shrinking the heap by one and growing the sorted suffix at the array’s tail — all inside the same array, $O(1)$ extra space.
• Worst case is $O(n \log n)$, guaranteed — no adversarial input, no randomization needed, unlike quicksort.
• Not stable; usually slower in practice than quicksort due to poor cache locality, but preferred when a worst-case guarantee matters.
• heapq gives the same asymptotics via a min-heap, but is built for a live priority queue, not specifically in-place array sorting.

Next: Counting, Radix, and Bucket Sort — non-comparison sorts that beat the $\Omega(n \log n)$ comparison lower bound entirely, when the keys are bounded integers.