Log inSign up
easyGeeksforGeeksNot Started

Build Heap

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an unsorted array arr of size N, rearrange its elements in-place so that it satisfies the Binary Max-Heap property: For every valid index i, arr[i] >= arr[2i + 1] and arr[i] >= arr[2i + 2].

Your goal is to build the Max-Heap efficiently in O(N) time using Floyd's heap construction.

Example 1 · Example 1: Standard Unsorted Array:

Input: arr = [4, 10, 3, 5, 1]
Output: [10, 5, 3, 4, 1]
Explanation: 1. Last non-leaf node is at index (5/2 - 1) = 1 (value 10). Children are at index 3 (5) and index 4 (1). 10 >= 5 and 10 >= 1, so already valid. 2. Move to index 0 (value 4). Children are index 1 (10) and index 2 (3). Largest is 10. Swap 4 and 10. 3. Sift down 4: children are index 3 (5) and index 4 (1). Swap 4 and 5. Result: [10, 5, 3, 4, 1]. Initial Tree: Max-Heap Tree: (4) (10) / \ / \ (10) (3) ===> (5) (3) / \ / \ (5) (1) (4) (1)

Constraints:

  • 1 <= N <= 105
  • -106 <= arr[i] <= 106

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Prove why Floyd's bottom-up build heap runs in O(N) time.
  • Implement the iterative sift-down (heapify) operation in-place.
  • Understand the difference between sift-up (O(N log N)) and sift-down (O(N)) construction.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Transform an arbitrary array into a binary heap in-place.
  • Need linear O(N) heap initialization instead of O(N log N).
  • Classic bottom-up heapify algorithm.

Algorithmic Decision Tree:

  • Inserting elements one by one using sift-up takes O(N log N) because most nodes are near the leaves and travel up high paths.
  • Sifting down from bottom-up takes O(N) because the vast majority of nodes are at the bottom where height is small (0 or 1).

Connected Patterns:

Heap SortCheck if Array Represents Min HeapKth Largest Element in an Array

1. Brute Force — Sift-Up Sequential Insertion

Intuition

Simulate inserting elements into a binary heap one by one. For each index i from 1 to N-1, compare with parent at (i-1)/2 and swap upwards while element is greater than parent.

When to apply: When elements arrive one at a time via a streaming source.

Algorithm

  1. Step 1: Loop i from 1 to N - 1.
  2. Step 2: While i > 0 and arr[i] > arr[(i - 1) / 2], swap arr[i] with arr[(i - 1) / 2].
  3. Step 3: Update i = (i - 1) / 2.
  4. Step 4: Continue until all elements have sifted up.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5class Solution {
6public:
7 void buildHeap(vector<int>& arr) {
8 int n = arr.size();
9 for (int i = 1; i < n; i++) {
10 int curr = i;
11 while (curr > 0) {
12 int parent = (curr - 1) / 2;
13 if (arr[curr] > arr[parent]) {
14 swap(arr[curr], arr[parent]);
15 curr = parent;
16 } else {
17 break;
18 }
19 }
20 }
21 }
22};
23
24int main() {
25 Solution sol;
26 vector<int> arr = {4, 10, 3, 5, 1};
27 sol.buildHeap(arr);
28 cout << "Max-Heap (Sift-Up): ";
29 for (int x : arr) cout << x << " ";
30 cout << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N log N) — O(N log N) because elements near leaves must traverse up the entire tree.
  • Space complexity: O(1) — O(1) auxiliary space as swaps are in-place.

Why Brute Force Doesn't Scale:

With N = 107, O(N log N) requires ~2.4 * 108 operations, whereas Floyd's algorithm requires ~2 * 107 operations.

Building a heap of 10 million elements takes ~45ms with Floyd's method versus ~600ms with successive sift-up.

2. Better — Sort Descending

Intuition

In a descending sorted array, for every index i, arr[i] >= arr[i+1] >= arr[2i+1] and arr[2i+2]. Thus, any descending array is a valid binary max-heap.

When to apply: When code brevity is the only goal and O(N log N) library sort is acceptable.

Algorithm

  1. Step 1: Sort the array in descending order using an efficient comparison sort.
  2. Step 2: Array automatically satisfies the max-heap property.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6class Solution {
7public:
8 void buildHeap(vector<int>& arr) {
9 sort(arr.begin(), arr.end(), greater<int>());
10 }
11};
12
13int main() {
14 Solution sol;
15 vector<int> arr = {4, 10, 3, 5, 1};
16 sol.buildHeap(arr);
17 cout << "Max-Heap (Sorted): ";
18 for (int x : arr) cout << x << " ";
19 cout << endl;
20 return 0;
21}

Time & Space Complexity

  • Time complexity: O(N log N) — O(N log N) for comparison sort.
  • Space complexity: O(1) auxiliary — O(1) auxiliary space beyond recursion stack.

3. Optimal — Floyd's Bottom-Up Sift-Down Algorithm

Intuition

Floyd's algorithm starts from the lowest non-leaf nodes and sifts them down. Since the number of nodes at height h is at most ceil(N / 2^(h+1)), the total work is sum_{h=0}^{log N} (N / 2^(h+1)) * O(h) = O(N sum_{h=0}^{infinity} h / 2h) = O(N).

When to apply: Standard optimal algorithm for building heaps and initializing heap sort.

Algorithm

  1. Step 1: Find the last non-leaf node index: start = (n / 2) - 1.
  2. Step 2: Loop i from start down to 0.
  3. Step 3: Define heapifyDown(i): set largest = i, left = 2i + 1, right = 2i + 2.
  4. Step 4: If left < n and arr[left] > arr[largest], largest = left.
  5. Step 5: If right < n and arr[right] > arr[largest], largest = right.
  6. Step 6: If largest != i, swap arr[i] and arr[largest], then continue sifting down at largest.
  7. Step 7: Array is now a valid Max-Heap in strictly O(N) time.

Interactive Trace for Build Heap

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Check node at index 1 (value 10)
Visual state
Values and pointers at this exact step
tree
Array Buffer RepresentationParent i → Left 2i+1, Right 2i+2
S
4
10
3
5
1
0
1
↑ curr
2
3
4
Binary Heap Tree Topology
4#n0
10#n1
3#n2
5#n3
1#n4
Check / comparison
10 >= 5 and 10 >= 1
Decision / next transition
Node 10 satisfies heap property. Move to index 0.
Why this step matters

Step 1: Check node at index 1 (value 10). Left child = 5, right child = 1.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5class Solution {
6public:
7 void heapifyDown(vector<int>& arr, int n, int i) {
8 while (true) {
9 int largest = i;
10 int left = 2 * i + 1;
11 int right = 2 * i + 2;
12
13 if (left < n && arr[left] > arr[largest]) largest = left;
14 if (right < n && arr[right] > arr[largest]) largest = right;
15
16 if (largest != i) {
17 swap(arr[i], arr[largest]);
18 i = largest;
19 } else {
20 break;
21 }
22 }
23 }
24
25 void buildHeap(vector<int>& arr) {
26 int n = arr.size();
27 for (int i = (n / 2) - 1; i >= 0; i--) {
28 heapifyDown(arr, n, i);
29 }
30 }
31};
32
33int main() {
34 Solution sol;
35 vector<int> arr = {4, 10, 3, 5, 1};
36 sol.buildHeap(arr);
37 cout << "Max-Heap (Floyd's O(N)): ";
38 for (int x : arr) cout << x << " ";
39 cout << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(N) — O(N) because the vast majority of nodes reside at low heights where sift-down cost is minimal.
  • Space complexity: O(1) — O(1) auxiliary space using iterative sift-down.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Successive Insertions (Sift-Up)O(N log N)O(1)Start with a heap of size 1 and iteratively sift up each subsequent element from index 1 to N-1.Leaves do the maximum work.
2.Better — Sort DescendingO(N log N)O(1) auxiliarySort the array in descending order. Any sorted descending array trivially satisfies the max-heap property.Comparison-based sorting lower bound.
3.Optimal — Floyd's Bottom-Up Sift-DownOptimalO(N)O(1) auxiliaryIterate from index (N/2 - 1) down to 0 and call maxHeapify (sift-down) on each node.None. Mathematically optimal.

Common Pitfalls & Crucial Edge Cases

Starting from N-1 instead of floor(N/2)-1

Leaves do not need sift-down; starting at N-1 wastes iterations.

Using Sift-Up instead of Sift-Down

Sift-up results in O(N log N) time.

Missing bounds check for right child

Must check right < n before accessing arr[right].

Crucial Edge Cases to Validate:

  • Single element array (N = 1) — Automatically satisfies max-heap; loop does not run.
  • Already sorted array (Ascending) — Inverts completely into valid max-heap.
  • Already valid Max-Heap — No swaps performed, runs in O(N).
  • Duplicate values — Handled gracefully by comparison conditions.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always derive the O(N) complexity using the geometric series sum to impress the interviewer.
  2. Clarify whether a Min-Heap or Max-Heap is requested.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does Floyd's bottom-up build-heap take O(N) time instead of O(N log N)?

Back to DSA Sheet