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.