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 heapqheapq directly.

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)heapify(arr, n, i) fixes that invariant at index ii, assuming both its subtrees are already valid heaps — it sifts the value at ii 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)

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 heapifyheapify 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))

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))

Step 2: repeatedly extract the max

The array’s root (arr[0]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))

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 heapifyheapify is written iteratively).

Watch one extract-and-sift-down cycle

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

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 `heapqheapq`

Python’s heapqheapq module is always a min-heap and works by mutating a list through repeated heappushheappush/heappopheappop 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)

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 heapqheapq pops into a fresh list uses $O(n)$ extra space (though heapq.heapifyheapq.heapify itself is in place). In practice: reach for heapqheapq when you need a live priority queue (items pushed/popped over time); reach for sorted()sorted() / .sort().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.

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

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. numsnums is an array of strings representing integers without leading zeros. Return the kkth largest as a string. Duplicates count separately.

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

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

Editorial

The strings are the point. Sorting them lexicographically would put "10""10" before "2""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)(len(s), s) is exactly numeric order.

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

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

In Python you could simply use key=intkey=int — integers are arbitrary-precision, so 100-digit values are fine. Worth mentioning, and the (len, s)(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]sorted(...)[-k]?” — $O(n \log n)$ ; fine here, but nlargestnlargest 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^51 <= len(s) <= 5 * 10^5, letters and digits.

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

Editorial

Count, then emit. Counter.most_common()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:

joinjoin over a generator, not result += ch * nresult += 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^5len(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)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)(-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)(-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 kk most frequent words, sorted by decreasing frequency and, for equal frequency, increasing lexicographic order.

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

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

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)(-count, word).

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

Note the use of nsmallestnsmallest with a negated count rather than nlargestnlargest. With nlargestnlargest 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: isis and sunnysunny both occur twice, and isis 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 nlargestnlargest?” — it would reverse the tie-break too. “Top kk frequent numbers (LC 347)?” — no tie-break specified, so it is easier.

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.
heapqheapq 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.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Heap Sort

What you’ll learn

Step 1: build a max-heap, in place

Step 2: repeatedly extract the max

Watch one extract-and-sift-down cycle

Contrast with heapqheapq

Time and space complexity

Practice — real LeetCode problems

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

LC 451 — Sort Characters By Frequency · Medium

LC 692 — Top K Frequent Words · Medium

Recap

Was this page helpful?

Contrast with `heapqheapq`