🎓 A1Learner
🔍

DSA Heap Sort

Heap sort is a sorting method that builds a max-heap and then moves the maximum into place again and again. A max-heap is a list where every parent is at least as large as its children.

Sifting one root down

Sifting down compares a value with its children. It swaps with the larger child and keeps going.

def sift_down(heap, root, end, swaps):
    while True:
        child = 2 * root + 1
        if child > end:
            return
        if child + 1 <= end and heap[child] < heap[child + 1]:
            child += 1
        if heap[root] < heap[child]:
            heap[root], heap[child] = heap[child], heap[root]
            swaps[0] += 1
            root = child
        else:
            return

heap = [3, 9, 5, 7, 8]
swaps = [0]
sift_down(heap, 0, len(heap) - 1, swaps)
print("heap:", heap)
print("swaps:", swaps[0])

Heapify builds the heap

Heapify starts at the last parent and sifts each value down. The root ends up holding the maximum.

def sift_down(heap, root, end, swaps):
    while True:
        child = 2 * root + 1
        if child > end:
            return
        if child + 1 <= end and heap[child] < heap[child + 1]:
            child += 1
        if heap[root] < heap[child]:
            heap[root], heap[child] = heap[child], heap[root]
            swaps[0] += 1
            root = child
        else:
            return

def heapify(nums):
    swaps = [0]
    start = len(nums) // 2 - 1
    for i in range(start, -1, -1):
        sift_down(nums, i, len(nums) - 1, swaps)
    return swaps[0]

nums = [4, 10, 3, 5, 1, 8]
used = heapify(nums)
print("heap:", nums)
print("maximum at root:", nums[0])
print("swaps:", used)

One extraction step

Extraction swaps the root with the last value. The heap then shrinks by one and sifts the new root down.

def sift_down(heap, root, end, swaps):
    while True:
        child = 2 * root + 1
        if child > end:
            return
        if child + 1 <= end and heap[child] < heap[child + 1]:
            child += 1
        if heap[root] < heap[child]:
            heap[root], heap[child] = heap[child], heap[root]
            swaps[0] += 1
            root = child
        else:
            return

heap = [10, 5, 8, 4, 1, 3]
swaps = [0]
heap[0], heap[5] = heap[5], heap[0]
sift_down(heap, 0, 4, swaps)
print("placed at the end:", heap[5])
print("heap part:", heap[:5])
print("sift swaps:", swaps[0])

Example

def sift_down(heap, root, end, swaps):
    while True:
        child = 2 * root + 1
        if child > end:
            return
        if child + 1 <= end and heap[child] < heap[child + 1]:
            child += 1
        if heap[root] < heap[child]:
            heap[root], heap[child] = heap[child], heap[root]
            swaps[0] += 1
            root = child
        else:
            return

def heap_sort(nums):
    swaps = [0]
    n = len(nums)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(nums, i, n - 1, swaps)
    heapify_swaps = swaps[0]
    print("after heapify:", nums)
    print("heapify swaps:", heapify_swaps)
    for end in range(n - 1, 0, -1):
        nums[0], nums[end] = nums[end], nums[0]
        swaps[0] += 1
        sift_down(nums, 0, end - 1, swaps)
    print("extraction swaps:", swaps[0] - heapify_swaps)
    return swaps[0]

nums = [6, 2, 9, 4, 7, 1, 8, 3]
print("start:", nums)
total = heap_sort(nums)
print("sorted:", nums)
print("total swaps:", total)

Key points

  • Heap sort sorts by building a max-heap and extracting the maximum repeatedly.
  • Sifting down swaps a value with its larger child until order is restored.
  • The children of index i sit at indices 2i + 1 and 2i + 2.
  • Heapify sifts down from the last parent up to the root.
  • Each extraction swaps the root with the last unsorted value.

In this example, a list of eight values is sorted with the from-scratch heap. Heapify sifts every parent down, and the printed list shows 9 at the root. Each extraction then swaps the root into the last unsorted slot. One extra swap is counted for each of those root exchanges. The sorted list and the two swap counts prove the heap did the sorting work.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

In the heap list, a node sits at index 2. Where are its two children?