Heap Concept Structure and Properties in DSA C++

Mental Model

A heap is a special tree where each parent is bigger (max heap) or smaller (min heap) than its children, keeping the biggest or smallest item always on top.

Analogy: Imagine a pile of boxes stacked so that the biggest box is always on top, and every box below is smaller or equal in size than the one above it.

       [50]
      /     \
   [30]     [20]
   /  \     /  \
 [15] [10] [8] [5]

Dry Run Walkthrough

Input: Build a max heap from array: [15, 10, 30, 50, 20, 8, 5]

Goal: Rearrange the array into a max heap so the largest value is at the root and heap property holds for all nodes.

Step 1: Start heapify from last parent node at index 2 (value 30)

[15, 10, 30, 50, 20, 8, 5]

Why: We begin from last parent to ensure subtrees below are heaps before fixing parents

Step 2: Compare 30 with children 8 and 5; 30 is largest, no swap

[15, 10, 30, 50, 20, 8, 5]

Why: No change needed as parent is already larger than children

Step 3: Move to parent at index 1 (value 10), compare with children 50 and 20

[15, 10, 30, 50, 20, 8, 5]

Why: Check if heap property holds at this node

Step 4: Swap 10 with largest child 50

[15, 50, 30, 10, 20, 8, 5]

Why: Parent must be larger than children in max heap

Step 5: Heapify subtree rooted at index 3 (value 10), compare with children none (leaf)

[15, 50, 30, 10, 20, 8, 5]

Why: No children to compare, subtree is heap

Step 6: Move to root at index 0 (value 15), compare with children 50 and 30

[15, 50, 30, 10, 20, 8, 5]

Why: Check if root satisfies heap property

Step 7: Swap 15 with largest child 50

[50, 15, 30, 10, 20, 8, 5]

Why: Root must be largest in max heap

Step 8: Heapify subtree rooted at index 1 (value 15), compare with children 10 and 20

[50, 15, 30, 10, 20, 8, 5]

Why: Fix heap property in subtree

Step 9: Swap 15 with largest child 20

[50, 20, 30, 10, 15, 8, 5]

Why: Parent must be larger than children

Step 10: Heapify subtree rooted at index 4 (value 15), no children to compare

[50, 20, 30, 10, 15, 8, 5]

Why: Leaf node, heap property holds

Result:

Final max heap array: [50, 20, 30, 10, 15, 8, 5]
Heap structure:
       [50]
      /     \
   [20]     [30]
   /  \     /  \
 [10] [15] [8] [5]

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void heapify(vector<int>& arr, int n, int i) {
    int largest = i; // Initialize largest as root
    int left = 2 * i + 1; // left child index
    int right = 2 * i + 2; // right child index

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // If right child is larger than largest so far
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // If largest is not root
    if (largest != i) {
        swap(arr[i], arr[largest]); // swap root and largest child
        heapify(arr, n, largest); // recursively heapify the affected subtree
    }
}

void buildMaxHeap(vector<int>& arr) {
    int n = arr.size();
    // Start from last parent node and heapify each
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

void printHeap(const vector<int>& arr) {
    for (int val : arr) {
        cout << val << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {15, 10, 30, 50, 20, 8, 5};
    buildMaxHeap(arr);
    printHeap(arr);
    return 0;
}

if (left < n && arr[left] > arr[largest])

compare left child with current largest to find max

if (right < n && arr[right] > arr[largest])

compare right child with current largest to find max

if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); }

swap parent with largest child and recursively fix subtree

for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); }

build heap by heapifying from last parent up to root

Output

50 20 30 10 15 8 5 

Complexity Analysis

Time: O(n) because heapify is called on n/2 nodes and each call takes O(log n) in worst case, but overall build heap is O(n)

Space: O(1) because heap is built in place without extra arrays

vs Alternative: Naive approach inserting elements one by one into heap costs O(n log n), build heap is more efficient at O(n)

Edge Cases

Empty array

No heap to build, function exits without changes

DSA C++

for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); }

Single element array

Heap is trivially valid, no swaps needed

DSA C++

for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); }

All elements equal

Heap property holds naturally, no swaps occur

DSA C++

if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); }

When to Use This Pattern

When you need quick access to the largest or smallest element repeatedly, recognize the heap pattern because it keeps that element at the root efficiently.

Common Mistakes

Mistake: Starting heapify from the root instead of last parent node
Fix: Start heapify from last parent node (n/2 - 1) down to root to ensure subtrees are heaps before parents

Mistake: Not recursively heapifying after swap
Fix: After swapping parent with child, recursively call heapify on the child index to fix subtree

Summary

A heap is a tree structure where parents are always larger (max heap) or smaller (min heap) than their children.

Use a heap when you need fast access to the largest or smallest item and efficient insertions/removals.

The key insight is to build the heap from the bottom up, fixing subtrees before parents to maintain the heap property.

Practice

1. What is the main property of a max-heap data structure?

easy

A. Every parent node is less than or equal to its children

B. Every parent node is greater than or equal to its children

C. All leaf nodes are at the same level

D. It is a complete binary tree with sorted elements

Solution

1. Step 1: Understand max-heap property

   A max-heap requires that each parent node's value is greater than or equal to its children's values.

2. Step 2: Compare options with definition

   Every parent node is greater than or equal to its children matches the max-heap property exactly, while others describe min-heap or unrelated properties.

3. Final Answer:

   Every parent node is greater than or equal to its children -> Option B

4. Quick Check:

   Max-heap property = Every parent ≥ children [OK]

Hint: Max-heap means parent ≥ children always [OK]

Common Mistakes:

• Confusing max-heap with min-heap property
• Thinking heap means sorted tree
• Assuming all leaf nodes must be at same level

2. Which of the following is the correct way to declare a max-heap using C++ STL?

easy

A. std::priority_queue<int> maxHeap;

B. std::priority_queue maxHeap;

C. std::priority_queue maxHeap;

D. std::priority_queue maxHeap;

Solution

1. Step 1: Recall default priority_queue behavior

   By default, std::priority_queue in C++ is a max-heap using std::less comparator.

2. Step 2: Check each declaration

   std::priority_queue<int> maxHeap; uses default max-heap. std::priority_queue maxHeap; uses std::greater, which creates min-heap. std::priority_queue maxHeap; uses std::list which is invalid container for priority_queue. std::priority_queue maxHeap; uses std::list which is invalid container for priority_queue.

3. Final Answer:

   std::priority_queue<int> maxHeap; -> Option A

4. Quick Check:

   Default priority_queue = max-heap [OK]

Hint: Default priority_queue is max-heap in C++ STL [OK]

Common Mistakes:

• Using std::greater for max-heap (it's for min-heap)
• Using invalid container like std::list
• Confusing comparator template parameters

3. What will be the output of the following C++ code snippet?

std::priority_queue<int> pq;
pq.push(10);
pq.push(5);
pq.push(20);
pq.push(1);
std::vector<int> result;
while (!pq.empty()) {
  result.push_back(pq.top());
  pq.pop();
}
for (int val : result) std::cout << val << " ";

medium

A. 10 20 5 1

B. 1 5 10 20

C. 20 10 5 1

D. 5 10 1 20

Solution

1. Step 1: Understand priority_queue behavior

   std::priority_queue by default is a max-heap, so top() returns the largest element.

2. Step 2: Trace push and pop operations

   Elements pushed: 10, 5, 20, 1. The popping order will be from largest to smallest: 20, 10, 5, 1.

3. Final Answer:

   20 10 5 1 -> Option C

4. Quick Check:

   Max-heap pop order = 20 10 5 1 [OK]

Hint: priority_queue pops largest first by default [OK]

Common Mistakes:

• Assuming priority_queue pops smallest first
• Confusing push order with pop order
• Ignoring default max-heap behavior

4. Identify the error in the following code snippet that tries to create a min-heap using C++ STL:

std::priority_queue<int> minHeap;
minHeap.push(3);
minHeap.push(1);
minHeap.push(4);
minHeap.push(2);
while (!minHeap.empty()) {
  std::cout << minHeap.top() << " ";
  minHeap.pop();
}

medium

A. priority_queue by default is a max-heap, so this code does not create a min-heap

B. Missing include directive for <queue>

C. Cannot push elements into priority_queue

D. The pop() function is used incorrectly

Solution

1. Step 1: Check default behavior of priority_queue

   By default, std::priority_queue is a max-heap, so it returns the largest element first.

2. Step 2: Analyze code intent vs behavior

   The code tries to create a min-heap but uses default priority_queue without comparator, so it behaves as max-heap.

3. Final Answer:

   priority_queue by default is a max-heap, so this code does not create a min-heap -> Option A

4. Quick Check:

   Default priority_queue = max-heap, not min-heap [OK]

Hint: Default priority_queue is max-heap, need comparator for min-heap [OK]

Common Mistakes:

• Assuming default priority_queue is min-heap
• Thinking pop() usage is wrong
• Ignoring need for comparator to create min-heap

5. You want to merge two max-heaps represented as arrays: heap1 = [40, 30, 20] and heap2 = [35, 25, 15]. Which approach correctly merges them into a valid max-heap?

hard

A. Sort both arrays and merge them in ascending order

B. Insert all elements of heap2 into heap1 one by one without rebuilding

C. Replace the root of heap1 with the root of heap2 and heapify once

D. Concatenate both arrays and then build a max-heap from the combined array

Solution

1. Step 1: Understand heap merge requirements

   To merge two heaps, simply concatenating is not enough; we must restore heap property by building a max-heap from combined elements.

2. Step 2: Evaluate options

   Concatenate both arrays and then build a max-heap from the combined array correctly concatenates and rebuilds heap. Insert all elements of heap2 into heap1 one by one without rebuilding inserts elements one by one but is less efficient. Sort both arrays and merge them in ascending order sorts ascending which breaks max-heap property. Replace the root of heap1 with the root of heap2 and heapify once replaces root incorrectly and does not fix heap.

3. Final Answer:

   Concatenate both arrays and then build a max-heap from the combined array -> Option D

4. Quick Check:

   Merge heaps by combining and heapifying [OK]

Hint: Merge heaps by combining arrays then heapify [OK]

Common Mistakes:

• Sorting arrays instead of heapifying
• Replacing root without fixing heap
• Inserting elements one by one inefficiently