Building a Heap from an Unordered Array

1. Two Approaches to Building a Heap

Imagine you have an array of numbers, say [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]. How would you turn this into a max-heap?

1. One-by-one Insertion ($O(N\log N)$): You could start with an empty heap and insert each element from the array. The first insertion is cheap, but as the heap grows, each subsequent insertion can take up to $O(\log k)$ time, where k is the current size of the heap. Summing this over all N elements gives a total time complexity of $O(N\log N)$.

2. The buildHeap Algorithm ($O(N)$): A much faster way is to treat the entire array as a complete (but not yet valid) binary tree and then fix it. This process is often called "heapifying" the array.

Let's watch a short video that contrasts these two methods and sets the stage for the efficient buildHeap algorithm.

As you saw, the heapify approach promises a linear time complexity, which is a significant improvement. Let's see how it works.

2. The buildHeap Algorithm: Bottom-Up Heapifying

The core idea behind the efficient buildHeap algorithm is surprisingly simple:

• A leaf node, by itself, is a valid heap of size one.
• Therefore, we only need to worry about the non-leaf nodes.

Given an array of size n, we can view it as a complete binary tree. The leaf nodes occupy the second half of the array. Specifically, in a 0-indexed array, the last non-leaf node is at index (n/2) - 1.

The algorithm proceeds as follows:

1. Start at the last non-leaf node: index i = (n/2) - 1.
2. Call the siftDown (or percolateDown) function on the element at index i. This ensures that the subtree rooted at i becomes a valid heap. Crucially, when we do this, the children of i are already roots of valid heaps (since we are moving backwards from the leaves).
3. Decrement i and repeat the process until you reach the root of the tree (index 0).

After siftDown has been called on the root, the entire array will satisfy the heap property.

Let's watch a detailed walkthrough of this process.

The siftDown operation is the same one we learned in the previous lesson for extractMax/extractMin. It takes a node, compares it with its children, and swaps it with the largest (for a max-heap) or smallest (for a min-heap) child if needed. The process repeats until the node is in its correct place.

3. Implementation in Java

The implementation of buildHeap is remarkably concise. It's a simple for loop that calls the siftDown method you've already seen.

Let's examine the code from the OpenDSA resource.

Here's what the buildHeap method typically looks like in Java for a heap stored in an ArrayList<T> named heap.

private void buildHeap() {
    // Start from the last non-leaf node and go up to the root
    for (int i = (heap.size() / 2) - 1; i >= 0; i--) {
        siftDown(i);
    }
}

This function would be called in the constructor if you were creating a heap from an existing collection.

4. Why is it O(N) Time? A Closer Look

At first glance, the complexity seems to be $O(N\log N)$. After all, we have a loop that runs about N/2 times, and inside it, we call siftDown, which takes $O(\log N)$ time in the worst case. So why is the total complexity linear?

The key is that siftDown rarely takes its worst-case time. The cost of siftDown on a node is proportional to the height of that node, not the height of the whole tree.

• Most nodes are at the bottom: In a complete binary tree, about half the nodes are leaves (height 0). They require 0 work.
• A quarter are one level up: About N/4 nodes are parents of leaves (height 1). They can only be sifted down by at most 1 level.
• An eighth are two levels up: About N/8 nodes have a height of 2. They can be sifted down by at most 2 levels.
• ...and so on. Only a single root node can be sifted down by the full height of the tree, $\log N$.

The total work is the sum of the heights of all nodes. This sum turns out to be a series that converges to a value proportional to N. Therefore, the total time complexity is $O(N)$.

Let's hear a final, clear explanation of this analysis.

Conclusion

You've just mastered a fundamental and highly efficient algorithm. While building a heap via repeated insertions is intuitive, the buildHeap algorithm is the superior choice when you have all the data at once.

Key Takeaways:

• You can build a heap from an unordered array in $O(N)$ linear time.
• The buildHeap algorithm works by treating the array as a complete binary tree and calling siftDown on each non-leaf node.
• The process iterates backwards, from the last non-leaf node ((n/2) - 1) up to the root (index 0).
• This bottom-up approach works because by the time you siftDown a node i, the subtrees rooted at its children are already valid heaps.
• The linear time complexity comes from the fact that most nodes are near the bottom of the tree and require very few swaps.

Preview of the Next Lesson:
Now that we have an efficient buildHeap method, we have the first major component for one of the most elegant sorting algorithms: Heap Sort. In the next lesson, we will combine buildHeap with the extractMax operation to sort an array in-place with an $O(N\log N)$ time complexity.