Building a Heap With n Pushes

Building a min-heap by pushing n items one at a time costs O(n log n) in the worst case, while sifting down every parent of the unordered array costs O(n). This card covers why the push loop is the slower build, how large the gap is when counted in swaps, and when a push loop is still the right choice.

A push places the new item at the end of the heap's array and sifts it up, swapping it with its parent while the parent is larger. The bottom-up build instead treats the whole unordered array as a complete tree and sifts down each parent, from the last parent back to the root.

The push loop is correct; it always ends with a valid heap. The trouble is its cost when items arrive in a bad order. With the 15 items 15 14 13 down to 1, every new item is smaller than everything already in the heap, so each one climbs to the root. A run of both builds counted the swaps.

The bottom-up column stays slightly under n, while the push column grows faster: for 262,143 items, n log2 n is about 4.7 million, and the push loop made 4.2 million swaps.

The difference comes from where the items are. Half the items in a complete tree sit in the bottom level. In the push loop, each of those enters at a leaf and may climb the whole height of about log2 n levels, so the many items pay the most. In the bottom-up build those leaves never move, and only the few items near the root travel far.

The two builds also leave different arrays, both valid heaps. On the 15 items the push loop left 1 6 2 9 7 5 3 15 12 13 8 14 10 11 4, and the bottom-up build left 1 5 2 7 6 3 9 8 12 14 11 4 10 13 15, so a question about the array after a build must name the build.

When every item is known before the heap is needed, build in one call: heapq.heapify(items) in Python, or new PriorityQueue<>(items) in Java, where items is a collection. Pushes remain right when items arrive over time, such as jobs added to a running scheduler: no build can include an item that has not arrived yet.