Course contentsShow
← Computer Science
Lesson 596 of 2,87214. Heaps and Priority QueuesFree lesson

Build Heap: Bottom-Up Construction

Efficiently convert unsorted array into heap using heapify-down from internal nodes.

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:

  1. Find the last internal node: index (n-1) // 2
  2. Loop backwards from that index down to 0
  3. For each position i, call heapify-down (downward bubbling)
  4. Each heapify-down "sinks" the element at i to 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.