Heap Sort: Using Binary Heap for Sorting
Heap sort is a comparison-based sorting algorithm that leverages the binary heap data structure to efficiently organize elements. Unlike quicksort, which can degrade to O(n²) on adversarial inputs,...
Key Insights
- Heap sort guarantees O(n log n) time complexity in all cases with O(1) auxiliary space, making it ideal for memory-constrained environments where quicksort’s worst-case behavior is unacceptable.
- The bottom-up heap construction algorithm runs in O(n) time, not O(n log n), because most nodes are near the bottom of the tree and require minimal sifting.
- While heap sort has excellent theoretical guarantees, its poor cache locality often makes it slower than quicksort in practice—choose it when you need predictable performance over raw speed.
Introduction to Heap Sort
Heap sort is a comparison-based sorting algorithm that leverages the binary heap data structure to efficiently organize elements. Unlike quicksort, which can degrade to O(n²) on adversarial inputs, heap sort maintains O(n log n) performance regardless of input distribution. It also beats mergesort on space efficiency, requiring only O(1) auxiliary memory since it sorts in-place.
So when should you reach for heap sort? Use it when you need guaranteed worst-case performance, when memory is tight, or when you’re already working with heap-based data structures. Skip it when cache performance matters more than theoretical guarantees—quicksort typically wins on modern hardware despite its worse asymptotic bound.
Understanding Binary Heaps
A binary heap is a complete binary tree that satisfies the heap property. In a max-heap, every parent node is greater than or equal to its children. In a min-heap, every parent is less than or equal to its children. For sorting in ascending order, we use a max-heap.
The elegant part of binary heaps is their array representation. We don’t need pointers or node objects—the tree structure is implicit in the array indices:
- Parent of node at index
i:(i - 1) / 2 - Left child of node at index
i:2 * i + 1 - Right child of node at index
i:2 * i + 2
This representation gives us cache-friendly memory access and zero pointer overhead.
class MaxHeap:
def __init__(self, arr=None):
self.heap = arr if arr else []
self.size = len(self.heap)
def get_parent(self, i):
return (i - 1) // 2
def get_left_child(self, i):
return 2 * i + 1
def get_right_child(self, i):
return 2 * i + 2
def has_left_child(self, i):
return self.get_left_child(i) < self.size
def has_right_child(self, i):
return self.get_right_child(i) < self.size
def swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
The size attribute is separate from the array length because during heap sort, we’ll shrink the logical heap while keeping sorted elements at the end of the same array.
The Heapify Operation
Heapify restores the heap property when a single node violates it. There are two variants: sift-up (used after insertion) and sift-down (used after extraction or during heap construction). For heap sort, we primarily use sift-down.
The sift-down operation assumes both subtrees of a node are valid heaps, but the node itself might be smaller than its children. We compare the node with its children, swap it with the larger child if necessary, and recurse down the tree.
def heapify(self, i):
"""
Restore heap property at index i, assuming subtrees are valid heaps.
Also known as sift-down or max-heapify.
"""
largest = i
left = self.get_left_child(i)
right = self.get_right_child(i)
# Check if left child exists and is greater than current largest
if left < self.size and self.heap[left] > self.heap[largest]:
largest = left
# Check if right child exists and is greater than current largest
if right < self.size and self.heap[right] > self.heap[largest]:
largest = right
# If largest is not the current node, swap and continue heapifying
if largest != i:
self.swap(i, largest)
self.heapify(largest)
The time complexity of heapify is O(log n) since we traverse at most the height of the tree. An iterative version avoids recursion overhead:
def heapify_iterative(self, i):
while True:
largest = i
left = self.get_left_child(i)
right = self.get_right_child(i)
if left < self.size and self.heap[left] > self.heap[largest]:
largest = left
if right < self.size and self.heap[right] > self.heap[largest]:
largest = right
if largest == i:
break
self.swap(i, largest)
i = largest
Building a Heap from an Array
The naive approach to building a heap—inserting elements one by one—takes O(n log n) time. But we can do better with bottom-up construction.
The insight is that leaf nodes (the bottom half of the array) are already valid heaps of size 1. We only need to heapify the internal nodes, starting from the last non-leaf and working up to the root.
def build_max_heap(self):
"""
Convert an arbitrary array into a valid max-heap.
Time complexity: O(n)
"""
# Start from the last non-leaf node and heapify each node up to root
# Last non-leaf is at index (n // 2) - 1
start_idx = (self.size // 2) - 1
for i in range(start_idx, -1, -1):
self.heapify(i)
Why is this O(n) instead of O(n log n)? Consider the work done at each level. Most nodes are near the bottom of the tree where the sift-down distance is short. Specifically, at height h, there are at most ⌈n/2^(h+1)⌉ nodes, and each requires O(h) work. Summing across all heights gives us O(n) total work.
This is one of those counterintuitive results that trips up many developers. The math works out because the number of nodes decreases exponentially as height increases, more than compensating for the linear increase in work per node.
The Heap Sort Algorithm
With the heap built, sorting is straightforward:
- The maximum element is at the root (index 0)
- Swap it with the last element in the heap
- Reduce the heap size by 1 (the max is now in its final position)
- Heapify the root to restore the heap property
- Repeat until the heap is empty
def heap_sort(arr):
"""
Sort an array in-place using heap sort.
Time: O(n log n), Space: O(1) auxiliary
"""
n = len(arr)
# Build max heap - O(n)
# Start from last non-leaf node
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract elements one by one - O(n log n)
for i in range(n - 1, 0, -1):
# Move current root (maximum) to end
arr[0], arr[i] = arr[i], arr[0]
# Heapify reduced heap (excluding sorted elements)
heapify(arr, i, 0)
return arr
def heapify(arr, heap_size, i):
"""
Heapify subtree rooted at index i.
heap_size is the size of the heap (may be less than len(arr))
"""
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < heap_size and arr[left] > arr[largest]:
largest = left
if right < heap_size and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, heap_size, largest)
Let’s trace through a small example with [4, 10, 3, 5, 1]:
- Build heap: After heapification, we get
[10, 5, 3, 4, 1] - First extraction: Swap 10 with 1, heapify →
[5, 4, 3, 1, 10] - Second extraction: Swap 5 with 1, heapify →
[4, 1, 3, 5, 10] - Third extraction: Swap 4 with 3, heapify →
[3, 1, 4, 5, 10] - Fourth extraction: Swap 3 with 1 →
[1, 3, 4, 5, 10]
The array is now sorted, and we used no extra space beyond a few variables.
Performance Analysis and Trade-offs
Heap sort’s O(n log n) guarantee in all cases is its primary advantage. Quicksort averages O(n log n) but degrades to O(n²) on sorted or nearly-sorted input without careful pivot selection. Mergesort matches heap sort’s time complexity but requires O(n) auxiliary space.
However, heap sort has a significant practical disadvantage: poor cache locality. When heapifying, we jump around the array following parent-child relationships. These jumps span increasingly large distances as we move up the tree, causing cache misses. Quicksort’s partitioning, by contrast, accesses memory sequentially.
Benchmarks typically show quicksort running 2-3x faster than heap sort on modern hardware, despite identical asymptotic complexity. This is the cache effect in action.
Heap sort is also unstable—equal elements may not preserve their original order. If stability matters, use mergesort or a stable variant of quicksort.
Choose heap sort when:
- You need guaranteed O(n log n) worst-case performance
- Memory is severely constrained
- You’re implementing a priority queue that occasionally needs full sorting
- You’re sorting in embedded systems with limited cache
Practical Applications
Beyond general-purpose sorting, heap-based algorithms excel at partial sorting problems. Finding the k largest elements in an array doesn’t require a full sort.
def find_k_largest(arr, k):
"""
Find the k largest elements using a min-heap of size k.
Time: O(n log k), Space: O(k)
"""
import heapq
if k >= len(arr):
return sorted(arr, reverse=True)
# Use a min-heap of size k
# Python's heapq is a min-heap
min_heap = arr[:k]
heapq.heapify(min_heap)
for i in range(k, len(arr)):
if arr[i] > min_heap[0]:
heapq.heapreplace(min_heap, arr[i])
return sorted(min_heap, reverse=True)
# Alternative: partial sort using heap sort principles
def partial_heap_sort(arr, k):
"""
Sort only the k largest elements to the end of the array.
Time: O(n + k log n)
"""
n = len(arr)
# Build max heap - O(n)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract only k elements - O(k log n)
for i in range(n - 1, n - k - 1, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
return arr[-k:] # k largest in sorted order
Priority queues—the most common heap application—power task schedulers, Dijkstra’s algorithm, Huffman coding, and event-driven simulations. Understanding heap sort deepens your intuition for these ubiquitous data structures.
The heap is one of those fundamental structures that appears everywhere once you know to look for it. Master heapify, and you’ve unlocked a versatile tool for problems far beyond sorting.