Editor

Heap sort in Python

Heap sort first arranges the list into a max-heap, a tree stored inside the list where every parent is at least as big as its children. Then it keeps swapping the biggest value to the end and repairing the heap.

The arrow keys step through it. Edit the code to try your own input.

How it works

  1. The list is read as a tree: the children of index root are at 2 * root + 1 and 2 * root + 2.
  2. sift_down swaps a value with its bigger child, again and again, until it is bigger than both children or has no children before end.
  3. The first loop calls sift_down on every parent, from the last one back to index 0. Now the biggest value is at nums[0].
  4. The second loop swaps nums[0] with nums[end], so the biggest value lands at the back. The heap is now one value shorter, and the new root is sifted down.

What to watch

  • Watch largest pick the bigger child before each swap down the tree.
  • Watch 10 rise to index 0 while the heap is built, then get swapped straight to the back.
  • Watch end move left: every bar from end onwards is in its final sorted place.

The code

def sift_down(nums, root, end):
    while True:
        largest = root
        left, right = 2 * root + 1, 2 * root + 2   # children of root
        if left < end and nums[left] > nums[largest]:
            largest = left
        if right < end and nums[right] > nums[largest]:
            largest = right
        if largest == root:
            return                 # bigger than both children: done
        nums[root], nums[largest] = nums[largest], nums[root]
        root = largest

def heap_sort(nums):
    n = len(nums)
    for i in range(n // 2 - 1, -1, -1):           # build the heap
        sift_down(nums, i, n)
    for end in range(n - 1, 0, -1):
        nums[0], nums[end] = nums[end], nums[0]   # biggest to the back
        sift_down(nums, 0, end)
    return nums

data = [4, 10, 3, 5, 1, 8]
print(heap_sort(data))
Output
[1, 3, 4, 5, 8, 10]

Open it in the editor · Python Program for Heap Sort, explained