Heapify a List in Place
Problem
Rearrange a list of numbers into a min-heap in place, without the heapq module, and return it. In a min-heap stored in a list, the children of index i are at 2i + 1 and 2i + 2, and every parent is at most each of its children. Use the bottom-up method: sift each parent down, starting from the last parent and moving towards the root, so the whole build runs in O(n).
Examples
Input: nums = [5, 3, 8, 1, 2]
Output: [1, 2, 8, 3, 5]
Why: 3 swaps with its child 1, then 5 sinks from the root past 1 and 2Input: nums = [9, 8, 7, 6, 5, 4, 3, 2, 1]
Output: [1, 2, 3, 6, 5, 4, 7, 8, 9]Input: nums = [42]
Output: [42]
Why: edge case, one element is already a heapHints
0 / 3
Leaves are heaps of size one already, so there is nothing to do for the second half of the list. The last index with a child is n // 2 - 1.
Sift down fixes one parent whose two subtrees are already heaps: swap it with its smaller child while that child is smaller than it, and follow it down.
Call sift down for i from n // 2 - 1 down to 0. Going backwards guarantees both subtrees of i were fixed before i is.
Solution
Bottom-up heapify treats the list as a tree and repairs it from the lowest parents upwards. Sift down only works when both subtrees of a node are already heaps, and processing indices from n // 2 - 1 down to 0 guarantees that, because every child has a larger index and was handled first. Each sift down swaps the node with its smaller child until neither child is smaller, which restores the heap order in that subtree. Pushing the values one by one would cost O(n log n), but here most nodes sit near the bottom and can only sink a level or two: the total work sums to O(n). Space is O(1) because everything happens inside the list.
def sift_down(a, i, n):
while True:
smallest, left, right = i, 2 * i + 1, 2 * i + 2
if left < n and a[left] < a[smallest]:
smallest = left
if right < n and a[right] < a[smallest]:
smallest = right
if smallest == i: # both children are larger: done
return
a[i], a[smallest] = a[smallest], a[i]
i = smallest # follow the value down
def heapify(a):
n = len(a)
for i in range(n // 2 - 1, -1, -1): # last parent back to the root
sift_down(a, i, n)
return a
print(heapify([5, 3, 8, 1, 2])) # -> [1, 2, 8, 3, 5]
print(heapify([9, 8, 7, 6, 5, 4, 3, 2, 1])) # -> [1, 2, 3, 6, 5, 4, 7, 8, 9]
print(heapify([42])) # -> [42]Stuck on the idea rather than the code? Heapify and Sift covers it.