Heap Sort and Heap Construction: The Complete Guide

Heap sort is the only comparison-based sorting algorithm that is both O(n log n) worst-case and O(1) extra space. It combines the best properties of merge sort (guaranteed performance) and quicksort (in-place). Understanding heap construction deeply also unlocks efficient solutions for “top K” problems.

Heap recap

A max-heap is a complete binary tree stored as an array where every parent is greater than or equal to its children.

# For node at index i (0-indexed):
# Parent:       (i - 1) // 2
# Left child:   2 * i + 1
# Right child:  2 * i + 2

The root (index 0) always contains the maximum element.

The sift-down operation

Sift-down fixes a single violation where a node is smaller than one of its children by swapping it downward.

def sift_down(arr, n, i):
    """
    Restore heap property by sifting node i downward.
    n is the heap size (may be less than len(arr) during sort).

    Time: O(log n) worst case (height of tree)
    """
    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]
        sift_down(arr, n, largest)  # Continue sifting down


# Iterative version (avoids recursion overhead)
def sift_down_iterative(arr, n, i):
    """
    Iterative sift-down. Same logic, no recursion stack.
    """
    while True:
        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:
            break

        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest

The sift-up operation

Sift-up fixes a violation where a node is larger than its parent by swapping it upward. This is used when inserting a new element.

def sift_up(arr, i):
    """
    Restore heap property by sifting node i upward.
    Time: O(log n) worst case
    """
    while i > 0:
        parent = (i - 1) // 2
        if arr[i] > arr[parent]:
            arr[i], arr[parent] = arr[parent], arr[i]
            i = parent
        else:
            break

Building a heap: O(n) vs O(n log n)

There are two ways to build a heap from an unsorted array. They look similar but have dramatically different performance.

Method 1: sift-up (top-down) - O(n log n)

Insert elements one by one, sifting each up to its correct position.

def build_heap_sift_up(arr):
    """
    Build heap by inserting elements one by one.
    Time: O(n log n) - SLOWER
    """
    for i in range(1, len(arr)):
        sift_up(arr, i)
    return arr

Each of the n elements might need to travel up to log(n) levels. Roughly n/2 elements are leaves, and each could sift up log(n) levels. Total work: approximately (n/2) * log(n) = O(n log n).

Method 2: sift-down (bottom-up) - O(n)

Start from the last non-leaf node and sift each node down.

def build_heap_sift_down(arr):
    """
    Build heap using bottom-up sift-down.
    Time: O(n) - FASTER

    Start from the last non-leaf node and work backwards.
    Leaves (indices n//2 to n-1) are already valid 1-element heaps.
    """
    n = len(arr)
    # Last non-leaf node is at index (n // 2 - 1)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, n, i)
    return arr

Why build-heap with sift-down is O(n)

This is one of the most commonly asked “why” questions in DSA interviews.

In a complete binary tree with n nodes:

• n/2 nodes are leaves - they do 0 swaps (already heaps).
• n/4 nodes are at height 1 - they do at most 1 swap each.
• n/8 nodes are at height 2 - they do at most 2 swaps each.
• …
• 1 node (root) is at height log(n) - it does at most log(n) swaps.

Total work:

T(n) = sum over h from 0 to log(n) of: (n / 2^(h+1)) * h

T(n) = n/2 * sum over h from 0 to infinity of: h / 2^h

The sum h/2^h from h=0 to infinity = 2

T(n) = n/2 * 2 = n = O(n)

Intuition: Most nodes are near the bottom and do very little work. Only a few nodes near the top do significant work. The work decreases geometrically as you go up, and the geometric sum converges.

def demonstrate_build_heap_cost(n):
    """
    Show the actual swap counts per level.
    """
    import math
    height = int(math.log2(n))
    total_swaps = 0

    for h in range(height + 1):
        nodes_at_height = n // (2 ** (h + 1))
        swaps_per_node = h
        level_swaps = nodes_at_height * swaps_per_node
        total_swaps += level_swaps
        print(f"  Height {h}: {nodes_at_height} nodes x {swaps_per_node} swaps = {level_swaps}")

    print(f"  Total swaps: {total_swaps} (n = {n})")
    print(f"  Ratio swaps/n: {total_swaps / n:.3f}")


print("Build-heap cost breakdown:")
demonstrate_build_heap_cost(1024)
# Height 0: 512 nodes x 0 swaps = 0
# Height 1: 256 nodes x 1 swaps = 256
# ...
# Total swaps ~= n

Compare with sift-up: In sift-up, the n/2 leaves potentially sift up log(n) levels each. That is (n/2) * log(n) = O(n log n). The leaves do the most work, which is the opposite situation.

Heap sort algorithm

Heap sort has two phases:

1. Build a max-heap from the array (O(n)).
2. Extract the max repeatedly: swap root with last element, reduce heap size, sift down (O(n log n)).

def heap_sort(arr):
    """
    Sort array in ascending order using heap sort.
    Time: O(n log n) guaranteed
    Space: O(1) - in-place
    """
    n = len(arr)

    # Phase 1: Build max-heap - O(n)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, n, i)

    # Phase 2: Extract elements one by one - O(n log n)
    for i in range(n - 1, 0, -1):
        # Move current root (maximum) to the end
        arr[0], arr[i] = arr[i], arr[0]
        # Sift down on reduced heap
        sift_down(arr, i, 0)

    return arr


# Example
data = [12, 11, 13, 5, 6, 7, 3, 1, 9, 2]
print(f"Original: {data}")
heap_sort(data)
print(f"Sorted:   {data}")
# Original: [12, 11, 13, 5, 6, 7, 3, 1, 9, 2]
# Sorted:   [1, 2, 3, 5, 6, 7, 9, 11, 12, 13]

Visualizing heap sort

def heap_sort_verbose(arr):
    """
    Heap sort with step-by-step output.
    """
    n = len(arr)

    # Build max-heap
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, n, i)
    print(f"Max-heap built: {arr}")

    # Extract
    for i in range(n - 1, 0, -1):
        print(f"  Swap root={arr[0]} with arr[{i}]={arr[i]}")
        arr[0], arr[i] = arr[i], arr[0]
        sift_down(arr, i, 0)
        print(f"  After sift-down: {arr[:i]} | sorted: {arr[i:]}")

    return arr


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

Partial sort: finding top K elements

One of heap sort’s greatest strengths is partial sorting. If you only need the K largest (or smallest) elements, you can stop after K extractions.

def top_k_largest(arr, k):
    """
    Find the k largest elements using a max-heap.
    Time: O(n + k log n) - much better than full sort when k << n
    Space: O(1)
    """
    n = len(arr)

    # Build max-heap in O(n)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, n, i)

    # Extract k elements in O(k log n)
    result = []
    heap_size = n
    for _ in range(k):
        result.append(arr[0])
        arr[0] = arr[heap_size - 1]
        heap_size -= 1
        sift_down(arr, heap_size, 0)

    return result


data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(f"Top 3: {top_k_largest(data[:], 3)}")
# Top 3: [9, 6, 5]

Using a min-heap for top K (memory-efficient for streams)

import heapq

def top_k_with_min_heap(arr, k):
    """
    Find k largest using a min-heap of size k.
    Time: O(n log k)
    Space: O(k) - great when n is huge (streaming data)
    """
    # Maintain a min-heap of size k
    # The heap always contains the k largest elements seen so far
    # The root (smallest in heap) is the k-th largest overall

    heap = arr[:k]
    heapq.heapify(heap)

    for num in arr[k:]:
        if num > heap[0]:
            heapq.heapreplace(heap, num)  # pop smallest, push new

    return sorted(heap, reverse=True)


data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(f"Top 3: {top_k_with_min_heap(data, 3)}")
# Top 3: [9, 6, 5]

Kth largest element

def find_kth_largest(nums, k):
    """
    Find the kth largest element.

    Method 1: Build max-heap, extract k times.
    Time: O(n + k log n)
    """
    # Build max-heap
    n = len(nums)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(nums, n, i)

    # Extract k-1 elements
    heap_size = n
    for _ in range(k - 1):
        nums[0] = nums[heap_size - 1]
        heap_size -= 1
        sift_down(nums, heap_size, 0)

    return nums[0]


def find_kth_largest_minheap(nums, k):
    """
    Method 2: Min-heap of size k.
    Time: O(n log k), Space: O(k)
    """
    heap = nums[:k]
    heapq.heapify(heap)

    for num in nums[k:]:
        if num > heap[0]:
            heapq.heapreplace(heap, num)

    return heap[0]


data = [3, 2, 1, 5, 6, 4]
print(f"2nd largest: {find_kth_largest(data[:], 2)}")       # 5
print(f"2nd largest: {find_kth_largest_minheap(data, 2)}")  # 5

Comparison with other O(n log n) sorts

Property	Heap Sort	Merge Sort	Quick Sort
Time (worst)	O(n log n)	O(n log n)	O(n^2)
Time (average)	O(n log n)	O(n log n)	O(n log n)
Time (best)	O(n log n)	O(n log n)	O(n log n)
Space	O(1)	O(n)	O(log n) stack
Stable?	No	Yes	No (usually)
Cache friendly?	No	Yes	Yes
Adaptive?	No	Natural merge sort	Yes (pattern-defeating)
Partial sort	Excellent	Poor	Quick-select

When to choose heap sort

• Guaranteed O(n log n) worst case with O(1) space.
• Partial sorting: when you only need top K elements.
• Embedded systems: when extra memory allocation is not allowed.

When to avoid heap sort

• Cache performance: heap sort jumps around the array (parent-child relationships), causing cache misses. Merge sort and quicksort access memory more sequentially.
• Stability: heap sort is not stable. Equal elements may change relative order.
• Practical speed: despite same asymptotic complexity, heap sort is typically 2-3x slower than quicksort in practice due to cache behavior.

Heap sort for descending order

For descending order, use a min-heap instead of a max-heap:

def sift_down_min(arr, n, i):
    """Sift-down for min-heap."""
    smallest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] < arr[smallest]:
        smallest = left
    if right < n and arr[right] < arr[smallest]:
        smallest = right

    if smallest != i:
        arr[i], arr[smallest] = arr[smallest], arr[i]
        sift_down_min(arr, n, smallest)


def heap_sort_descending(arr):
    """
    Sort in descending order using min-heap.
    """
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        sift_down_min(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        sift_down_min(arr, i, 0)

    return arr


data = [4, 10, 3, 5, 1]
print(heap_sort_descending(data))
# [10, 5, 4, 3, 1]

Using Python’s heapq module

Python’s heapq module provides a min-heap. For a max-heap, negate the values.

import heapq

def heap_sort_pythonic(arr):
    """
    Heap sort using Python's heapq module.
    Note: this uses O(n) extra space (not in-place).
    """
    heapq.heapify(arr)  # O(n) in-place
    return [heapq.heappop(arr) for _ in range(len(arr))]


data = [4, 10, 3, 5, 1]
print(heap_sort_pythonic(data))  # [1, 3, 4, 5, 10]

Complexity summary

Operation	Time	Notes
Build heap (sift-down)	O(n)	Bottom-up, optimal
Build heap (sift-up)	O(n log n)	Top-down, suboptimal
Heap sort total	O(n log n)	Build O(n) + extract O(n log n)
Insert (sift-up)	O(log n)	Single element
Extract max/min	O(log n)	Root removal + sift-down
Top K elements	O(n + k log n)	Build heap + k extractions
Top K with min-heap	O(n log k)	Streaming-friendly

Practice problems

Problem	Difficulty	Key Technique
Sort an Array (LC 912)	Medium	Full heap sort
Kth Largest Element (LC 215)	Medium	Partial sort or min-heap
Top K Frequent Elements (LC 347)	Medium	Min-heap of size k
Merge K Sorted Lists (LC 23)	Hard	Min-heap for merging
Find Median from Data Stream (LC 295)	Hard	Two heaps
Sort Colors (LC 75)	Medium	Not heap sort (use 3-way partition)
Last Stone Weight (LC 1046)	Easy	Max-heap simulation
K Closest Points to Origin (LC 973)	Medium	Max-heap of size k

Key takeaways

1. Build-heap with sift-down is O(n) because most nodes are near the bottom and do minimal work. Sift-up is O(n log n) because most nodes are near the bottom and must travel far up.
2. Heap sort is the only comparison sort that is O(n log n) worst-case and O(1) space.
3. In practice, heap sort is slower than quicksort and merge sort due to poor cache locality.
4. Heap sort excels at partial sorting (top K problems).
5. Python’s heapq.heapify() uses the O(n) sift-down approach.