Heapify: Sifting Up and Sifting Down

INSERT 2 into a min-heap
   before      : [3, 5, 17, 9, 11, 25, 30] | heap: True
   appended    : [3, 5, 17, 9, 11, 25, 30, 2] | heap: False   (shape is fine, order is not)
    swap index 7 with parent 3 -> [3, 5, 17, 2, 11, 25, 30, 9]
    swap index 3 with parent 1 -> [3, 2, 17, 5, 11, 25, 30, 9]
    swap index 1 with parent 0 -> [2, 3, 17, 5, 11, 25, 30, 9]
   after       : [2, 3, 17, 5, 11, 25, 30, 9] | heap: True

REMOVE the best from that heap
   took 2, moved 9 to the root: [9, 3, 17, 5, 11, 25, 30] | heap: False
    swap index 0 with child 1 -> [3, 9, 17, 5, 11, 25, 30]
    swap index 1 with child 3 -> [3, 5, 17, 9, 11, 25, 30]
   after       : [3, 5, 17, 9, 11, 25, 30] | heap: True

Follow the insertion. 2 was appended at index 7, then rose through indices 3 and 1 to reach the root, three swaps for a tree of height 3. The order property was broken immediately after the append, exactly as chapter 82 said, and the shape never was.

Why sifting down must take the better child

def holds(heap):
    n = len(heap)
    return all(heap[i] <= heap[c]
               for i in range(n) for c in (2 * i + 1, 2 * i + 2) if c < n)


def sift_down_correct(heap, i):
    n = len(heap)
    while True:
        left, right, best = 2 * i + 1, 2 * i + 2, i
        if left < n and heap[left] < heap[best]:
            best = left
        if right < n and heap[right] < heap[best]:
            best = right
        if best == i:
            return
        heap[i], heap[best] = heap[best], heap[i]
        i = best


def sift_down_wrong(heap, i):
    """Swaps with the FIRST child that is better, not the BETTER child."""
    n = len(heap)
    while True:
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and heap[left] < heap[i]:
            heap[i], heap[left] = heap[left], heap[i]
            i = left
        elif right < n and heap[right] < heap[i]:
            heap[i], heap[right] = heap[right], heap[i]
            i = right
        else:
            return


start = [20, 5, 3, 8, 9, 7, 6]
for name, routine in (("correct", sift_down_correct), ("wrong  ", sift_down_wrong)):
    heap = list(start)
    routine(heap, 0)
    print("%s: %s | a valid heap: %s" % (name, heap, holds(heap)))

print()
print("the wrong version swapped 20 with its LEFT child 5, but 3 was smaller.")
print("5 then sat above 3, which breaks the order property at the root.")

correct: [3, 5, 6, 8, 9, 7, 20] | a valid heap: True
wrong  : [5, 8, 3, 20, 9, 7, 6] | a valid heap: False

the wrong version swapped 20 with its LEFT child 5, but 3 was smaller.
5 then sat above 3, which breaks the order property at the root.

The wrong version produced an array that is not a heap, and it did so without any error. 5 ended up at the root while 3 sits below it. That is why the rule is "swap with the better of the two children", not "swap with a child that is better".

The costs

Sift down does about twice the comparisons of sift up per level, because it examines two children rather than one parent. Both are O(log n) and the constant difference is why building a heap is done with sift down in chapter 85 rather than with repeated insertion.

Quick revision

• Two repairs, two directions. Sift up after an insertion at the end; sift down after the last element is

moved to the root.

• Sift up: while better than the parent, swap and move up. One comparison per level.
• Sift down: find the better of the two children; if it is better than the current value, swap and move

down. Two comparisons per level.

• Swapping with the first better child rather than the better child produces an array that is not a heap,

silently.

• The shape is never broken by either operation; only the order is repaired.
• Both are O(log n), so insert and remove are O(log n) and peek is O(1).

Test yourself

1. When is each direction used? Sift up after inserting at the end of the array. Sift down after removing the root and moving the last element into its place.

2. Write sift up. While the index is not 0 and the value is better than its parent, swap the two and move to the parent's index.

3. Write sift down, and state the rule that is easy to get wrong. Find the better of the two children; if it is better than the current value, swap and continue from there. The rule is to swap with the BETTER child, not merely with a child that is better.

4. What happens if you swap with the first better child instead? The result is not a heap, and no error is raised. In the run, 5 ended at the root while 3 was below it.

5. Which operation does more comparisons per level, and why? Sift down, because it must examine both children, where sift up examines only the parent.

6. Give the costs of insert, remove and peek, with their parts. Insert: append O(1) then sift up O(log n), so O(log n). Remove: take the root, move the last element there, shorten, then sift down O(log n), so O(log n). Peek: O(1).