Push and Pop With Sift-Up and Sift-Down

A min-heap adds an item by placing it in the one free position and swapping it upward, and removes its smallest item by moving the last item to the root and swapping it downward. This card covers both operations, called sift-up and sift-down, traced one swap at a time on a small heap stored as an array.

A min-heap is a complete binary tree, filled level by level from the left, in which every parent is no larger than its children. In the array, the parent of index i is at (i - 1) // 2 and its children are at 2i + 1 and 2i + 2. Both operations restore the shape first, which is always possible in one move, and then repair heap order. The item that moved can only be out of order along one path, so the repair walks that path and stops as soon as the order holds. The heap starts as the array 1 3 5 7 4 8.

A run of both operations, printing the array after each swap, produced the same arrays: 1 3 2 7 4 8 5 after the push, and 2 3 5 7 4 8 after the pop.

Each operation does at most one swap per level, and a complete tree of n items has about log2 n levels, so push and pop both cost O(log n). The step most often done wrong is the choice of child in sift-down. Swapping 5 with the left child out of habit would give 3 5 2 7 4 8, which puts 3 above 2 at the root and breaks heap order. Sift-up never has that choice, because every node below the root has exactly one parent.