How a Heap Works: Sift Up and Sift Down
28 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A heap keeps the smallest value ready at index 0 without keeping the whole list sorted. Python's heapq hides how. Here you build the moves yourself: sift up, sift down and heapify.
The heap rule and the list
A min-heap is a list in which every item is less than or equal to its two children, so the smallest item is at index 0. Only parents and children are ordered; the rest of the list is not sorted.
A task queue must hand out the most urgent task first. A sorted list does that, but adding to it is slow. A heap keeps just enough order: no parent is larger than its children, so the smallest is at index 0.
heap = [2, 5, 3, 9, 6, 8, 4]i = 1print("value", heap[i])print("parent index", (i - 1) // 2)print("child indexes", 2 * i + 1, 2 * i + 2)Example 1 · A heap is not a sorted list
import heapq
heap = []for value in [7, 3, 9, 1, 5]: heapq.heappush(heap, value)print(heap)print(sorted(heap))[1, 3, 9, 7, 5] [1, 3, 5, 7, 9]
What this code does
- The smallest value, 1, is at index 0. The rest is only partly ordered: 9 comes before 7.
- Only
heap[0]is guaranteed. To read in order you must pop, or sort a copy.
A heap is a list that is read as a tree. Index 0 is the top. The children of index i sit at 2i + 1 and 2i + 2, and the parent sits at (i - 1) // 2, so no pointers are stored. The heapq module from the Collections lesson on priority queues works on exactly this layout.
Sift up: adding a value
Sift up moves a value at index i towards the top by swapping it with its parent while it is smaller than that parent. It restores the heap rule after an append.
To add a value, put it at the end of the list, which is the next free spot in the tree. It may be smaller than its parent. Swap it upward until its parent is not larger.
def sift_up(heap, i): while i > 0: parent = (i - 1) // 2 if heap[parent] <= heap[i]: break heap[parent], heap[i] = heap[i], heap[parent] i = parentExample 2 · Push, step by step
def sift_up(heap, i): while i > 0: parent = (i - 1) // 2 if heap[parent] <= heap[i]: break heap[parent], heap[i] = heap[i], heap[parent] i = parent
def sift_down(heap, i, size): while True: smallest = i for child in (2 * i + 1, 2 * i + 2): if child < size and heap[child] < heap[smallest]: smallest = child if smallest == i: return heap[i], heap[smallest] = heap[smallest], heap[i] i = smallest
def push(heap, value): heap.append(value) sift_up(heap, len(heap) - 1)
def pop(heap): top = heap[0] last = heap.pop() if heap: heap[0] = last sift_down(heap, 0, len(heap)) return top
heap = []for value in [7, 3, 9, 1]: push(heap, value) print(heap)[7] [3, 7] [3, 7, 9] [1, 3, 9, 7]
What this code does
- Pushing 3 swaps it above 7. Pushing 1 climbs two levels: past 7, then past 3.
- Each push moved a value up along one branch only, never across the whole list.
A new value climbs at most the height of the tree, about log2(n) levels. So a push costs O(log n) time, and the usual case is much less because most values stay near the bottom.
Sift down: removing the smallest
Sift down moves a value at index i towards the bottom by swapping it with its smaller child while a child is smaller than it. It restores the heap rule after the top is replaced.
The smallest value is at index 0. Remove it by moving the last value to the top and pushing it down. At each step swap it with the smaller child, until both children are larger.
def sift_down(heap, i, size): while True: smallest = i for child in (2 * i + 1, 2 * i + 2): if child < size and heap[child] < heap[smallest]: smallest = child if smallest == i: return heap[i], heap[smallest] = heap[smallest], heap[i] i = smallestExample 3 · Pop with sift down
def sift_up(heap, i): while i > 0: parent = (i - 1) // 2 if heap[parent] <= heap[i]: break heap[parent], heap[i] = heap[i], heap[parent] i = parent
def sift_down(heap, i, size): while True: smallest = i for child in (2 * i + 1, 2 * i + 2): if child < size and heap[child] < heap[smallest]: smallest = child if smallest == i: return heap[i], heap[smallest] = heap[smallest], heap[i] i = smallest
def push(heap, value): heap.append(value) sift_up(heap, len(heap) - 1)
def pop(heap): top = heap[0] last = heap.pop() if heap: heap[0] = last sift_down(heap, 0, len(heap)) return top
heap = [1, 3, 9, 7, 5]top = pop(heap)print("popped", top, "heap", heap)popped 1 heap [3, 5, 9, 7]
What this code does
- The last value, 5, goes to the top and sinks. It swaps with the smaller child, 3, and then stops because 7 is larger.
- The result [3, 5, 9, 7] is a valid heap again.
It swaps with the smaller child so the new parent is not larger than the other child. The check child < size stops at the end of the list. A pop costs O(log n) time and no extra space.
Building a heap by hand
Heapify turns an unordered list into a heap in O(n) time by calling sift down on each parent from the last one back to index 0. Pushing n items one by one costs O(n log n).
To heapify a list, you could push the values one by one. A faster way sifts down every parent, starting from the last parent and moving back to index 0. Leaves are already one-item heaps.
def build_heap(items): heap = list(items) for i in range(len(heap) // 2 - 1, -1, -1): sift_down(heap, i, len(heap)) return heapExample 4 · Build by hand and compare with heapq
def sift_up(heap, i): while i > 0: parent = (i - 1) // 2 if heap[parent] <= heap[i]: break heap[parent], heap[i] = heap[i], heap[parent] i = parent
def sift_down(heap, i, size): while True: smallest = i for child in (2 * i + 1, 2 * i + 2): if child < size and heap[child] < heap[smallest]: smallest = child if smallest == i: return heap[i], heap[smallest] = heap[smallest], heap[i] i = smallest
def push(heap, value): heap.append(value) sift_up(heap, len(heap) - 1)
def pop(heap): top = heap[0] last = heap.pop() if heap: heap[0] = last sift_down(heap, 0, len(heap)) return top
def build_heap(items): heap = list(items) for i in range(len(heap) // 2 - 1, -1, -1): sift_down(heap, i, len(heap)) return heap
data = [9, 4, 7, 1, 8, 2]by_hand = build_heap(data)library = data[:]import heapqheapq.heapify(library)print(by_hand)print(by_hand == library)[1, 4, 2, 9, 8, 7] True
What this code does
data[:]copies the list, becauseheapifychanges its argument in place.- Both versions give the same list, because they follow the same sift-down rule.
Example 5 · Heap sort with a hand-made heap
def sift_up(heap, i): while i > 0: parent = (i - 1) // 2 if heap[parent] <= heap[i]: break heap[parent], heap[i] = heap[i], heap[parent] i = parent
def sift_down(heap, i, size): while True: smallest = i for child in (2 * i + 1, 2 * i + 2): if child < size and heap[child] < heap[smallest]: smallest = child if smallest == i: return heap[i], heap[smallest] = heap[smallest], heap[i] i = smallest
def push(heap, value): heap.append(value) sift_up(heap, len(heap) - 1)
def pop(heap): top = heap[0] last = heap.pop() if heap: heap[0] = last sift_down(heap, 0, len(heap)) return top
def heap_sort(items): heap = [] for value in items: push(heap, value) return [pop(heap) for _ in range(len(heap))]
print(heap_sort([40, 10, 30, 20, 50, 10]))[10, 10, 20, 30, 40, 50]
What this code does
- Push everything, then pop everything. Each pop returns the smallest value left, so the results come out sorted.
- Time is O(n log n) and the heap needs O(n) space. In real code
sortedis simpler; this shows how a heap works.
Most nodes are near the bottom and sift down only a step or two, so the total work is O(n), not O(n log n). This is what heapq.heapify does, in place and in C.
Next step
Check your understanding
11 quick questions