Build Heap: Bottom-Up Construction
What you'll learn: How to efficiently transform an unsorted array into a valid heap structure in linear time.
The Core Idea
Instead of inserting elements one-by-one into an empty heap (which costs O(n log n) total), we can convert an unsorted array into a heap much faster using bottom-up construction. The key insight: start with the array as-is, then work backwards from the last internal node, applying heapify-down to each one.
Why Start from Internal Nodes?
Leaf nodes (roughly the second half of the array) are already trivial heaps of size 1—they satisfy the heap property by default. We only need to fix the internal nodes, starting from the bottom and moving toward the root. This ensures that when we heapify a node, its children are already valid heaps.
The Process
Given an array of size n:
- Find the last internal node: index
(n-1) // 2 - Loop backwards from that index down to 0
- For each position
i, call heapify-down (downward bubbling) - Each heapify-down "sinks" the element at
ito its correct position
Why this works: By processing nodes bottom-up, when we heapify-down at position i, both child subtrees are already valid heaps. We just need to fix the current node's relationship with its children.
Time Complexity
This approach takes O(n) time—not O(n log n)! Most nodes are near the bottom (short heapify paths), so the work decreases as we move up the tree. The mathematical analysis shows this sums to linear time.
Key Takeaway: Build heap using bottom-up construction processes internal nodes in reverse order with heapify-down, achieving O(n) time—significantly faster than repeated insertion for initializing a heap from existing data.