Heap sort turns the array into a binary max-heap and then repeatedly moves the maximum to the end of the array. It is a rare sort with a guaranteed O(n log n) worst case, O(1) extra memory and no recursion. Here the heap is only a tool for sorting; the structure itself and the heapq module are covered in heaps and heapq.
A heap in an array
A max-heap is a binary tree in which every parent is not smaller than its children; the root is the maximum. It is stored in an array without pointers: the children of i are 2i + 1 and 2i + 2, its parent is (i - 1) // 2. The levels of the tree lie one after another.
a = [10, 5, 7, 4, 1, 3, 2]
for i in range(len(a)):
left, right = 2 * i + 1, 2 * i + 2
parent = (i - 1) // 2
kids = [a[k] for k in (left, right) if k < len(a)]
print(i, a[i], "parent", a[parent] if i else None, "children", kids)
def is_max_heap(a):
return all(a[(i - 1) // 2] >= a[i] for i in range(1, len(a)))
print(is_max_heap(a), is_max_heap([1, 5, 3]))0 10 parent None children [5, 7]
1 5 parent 10 children [4, 1]
2 7 parent 10 children [3, 2]
3 4 parent 5 children []
4 1 parent 5 children []
5 3 parent 7 children []
6 2 parent 7 children []
True Falsesift_down
sift_down(a, i, n) sinks the node i inside the heap a[:n]: it swaps the node with the larger child until the node is not smaller than its children. The time is the height of the heap, O(log n).
