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, making it easy to find the biggest or smallest item quickly.

Analogy: Imagine a pyramid of boxes where each box is heavier than the boxes below it, so the heaviest box is always on top and easy to grab.

       10
      /  \
     5    3
    / \  / \
   2  1 4  null

Dry Run Walkthrough

Input: array: [10, 5, 3, 2, 1, 4] for checking max heap property

Goal: Show the heap structure and verify the max heap property where each parent is greater than its children

Step 1: Start with array representation of heap

[10, 5, 3, 2, 1, 4]

Why: Heap is stored as an array where parent and children positions follow a pattern

Step 2: Map array to tree structure

       10
      /  \
     5    3
    / \  / \
   2  1 4  null

Why: Visualizing as tree helps understand parent-child relationships

Step 3: Check parent 10 against children 5 and 3

10 > 5 and 10 > 3, property holds

Why: Max heap requires parent to be greater than children

Step 4: Check parent 5 against children 2 and 1

5 > 2 and 5 > 1, property holds

Why: Each subtree also follows max heap property

Step 5: Check parent 3 against child 4

3 < 4, max heap property violated

Why: In max heap, parent must be greater than or equal to children; here 3 < 4 violates it

Result:

Heap tree:
       10
      /  \
     5    3
    / \  / \
   2  1 4  null
Max heap property holds except at node 3 and child 4, so this is not a valid max heap

Annotated Code

DSA C

#include <stdio.h>

// Function to print heap as array
void printHeap(int heap[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", heap[i]);
    }
    printf("\n");
}

// Function to check max heap property
int isMaxHeap(int heap[], int size) {
    for (int i = 0; i <= (size - 2) / 2; i++) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        // Check left child
        if (left < size && heap[i] < heap[left]) {
            return 0; // Not max heap
        }

        // Check right child
        if (right < size && heap[i] < heap[right]) {
            return 0; // Not max heap
        }
    }
    return 1; // Is max heap
}

int main() {
    int heap[] = {10, 5, 3, 2, 1, 4};
    int size = sizeof(heap) / sizeof(heap[0]);

    printf("Heap array: ");
    printHeap(heap, size);

    if (isMaxHeap(heap, size)) {
        printf("This is a valid max heap.\n");
    } else {
        printf("This is NOT a valid max heap.\n");
    }

    return 0;
}

for (int i = 0; i <= (size - 2) / 2; i++) {

iterate over all parent nodes to check heap property

if (left < size && heap[i] < heap[left]) {

check if parent is smaller than left child -- violates max heap

if (right < size && heap[i] < heap[right]) {

check if parent is smaller than right child -- violates max heap

Output

Heap array: 10 5 3 2 1 4 

This is NOT a valid max heap.

Complexity Analysis

Time: O(n) because we check each parent node once to verify heap property

Space: O(1) because we only use a few variables, no extra data structures

vs Alternative: Naive approach might check all pairs repeatedly, costing O(n log n), this is efficient linear check

Edge Cases

Empty heap (size 0)

Returns valid heap since no elements to violate property

DSA C

for (int i = 0; i <= (size - 2) / 2; i++) {

Single element heap

Always valid max heap because no children

DSA C

for (int i = 0; i <= (size - 2) / 2; i++) {

Heap with duplicate values

Valid if parent is >= children, duplicates allowed

DSA C

if (heap[i] < heap[left]) {

When to Use This Pattern

When you see a problem asking for quick access to largest or smallest element with partial order, think of heap structure because it keeps the biggest or smallest at the top efficiently.

Common Mistakes

Mistake: Confusing array indexing for parent and children positions
Fix: Remember left child = 2*i + 1, right child = 2*i + 2, parent = (i-1)/2

Mistake: Assuming heap is a sorted tree
Fix: Heap only guarantees parent-child order, not full sorted order

Summary

Heap is a tree-based structure where each parent is bigger (max heap) or smaller (min heap) than its children.

Use heap when you need fast access to the largest or smallest element.

The key insight is that heap property applies locally between parent and children, not globally sorted.

Practice

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

easy

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

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

C. All leaf nodes have the same value

D. The tree is always a complete binary tree but unordered

Solution

1. Step 1: Understand max-heap property

   A max-heap requires each parent node to be greater than or equal to its children to maintain the heap order.

2. Step 2: Check other options

   Every parent node is less than or equal to its children describes a min-heap, C is not true for heaps, and D is partially true but incomplete without heap order.

3. Final Answer:

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

4. Quick Check:

   Max-heap = Parent ≥ Children [OK]

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

Common Mistakes:

• Confusing max-heap with min-heap property
• Thinking all leaf nodes have same value
• Ignoring heap order property

2. Which of the following is the correct way to represent a heap in C using an array?

easy

A. Parent at index i, left child at i/2, right child at i/2 + 1

B. Parent at index i, left child at i - 1, right child at i + 1

C. Parent at index i, left child at 2*i + 1, right child at 2*i + 2

D. Parent at index i, left child at 2*i, right child at 2*i + 1

Solution

1. Step 1: Recall array indexing for heap

   In zero-based arrays, left child index = 2*i + 1 and right child index = 2*i + 2 for parent at i.

2. Step 2: Verify options

   Parent at index i, left child at 2*i + 1, right child at 2*i + 2 matches zero-based indexing. Parent at index i, left child at 2*i, right child at 2*i + 1 is for one-based indexing. Options A and C are incorrect formulas.

3. Final Answer:

   Parent at index i, left child at 2*i + 1, right child at 2*i + 2 -> Option C

4. Quick Check:

   Zero-based heap indexing = 2*i+1, 2*i+2 [OK]

Hint: Zero-based heap uses 2*i+1 and 2*i+2 for children [OK]

Common Mistakes:

• Using one-based indexing formulas in zero-based arrays
• Mixing up left and right child formulas
• Using division instead of multiplication for child indices

3. Consider the following max-heap array representation: [40, 30, 35, 15, 10, 25]. What will be the array after inserting 50 and re-heapifying?

medium

A. [50, 30, 40, 15, 10, 25, 35]

B. [40, 30, 35, 15, 10, 25, 50]

C. [50, 40, 35, 15, 30, 25, 10]

D. [40, 35, 30, 15, 10, 25, 50]

Solution

1. Step 1: Insert 50 at the end

   Array becomes [40, 30, 35, 15, 10, 25, 50].

2. Step 2: Re-heapify by bubbling up 50

   Parent of index 6 is (6-1)//2=2 (35 < 50), swap 6 and 2: [40, 30, 50, 15, 10, 25, 35]. Now at 2, parent 0 (40 < 50), swap 2 and 0: [50, 30, 40, 15, 10, 25, 35]. Heap property restored.

3. Final Answer:

   [50, 30, 40, 15, 10, 25, 35] -> Option A

4. Quick Check:

   Insert 50, bubble up to root [OK]

Hint: Insert at end, bubble up until parent ≥ node [OK]

Common Mistakes:

• Not bubbling up after insertion
• Swapping with wrong parent index
• Leaving new element at the end without re-heapify

4. The following C code snippet is intended to heapify a subtree rooted at index i in a max-heap array arr of size n. What is the error?

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

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

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

medium

A. Swapping elements before checking if largest changed

B. Incorrect calculation of left and right child indices

C. Missing base case to stop recursion

D. No error; code correctly heapifies the subtree

Solution

1. Step 1: Analyze child index calculation

   Left and right child indices are correctly calculated as 2*i+1 and 2*i+2 for zero-based arrays.

2. Step 2: Check recursion and swapping logic

   Swapping happens only if largest changes, then recursive call heapifies the affected subtree. No base case needed explicitly as recursion stops when largest == i.

3. Final Answer:

   No error; code correctly heapifies the subtree -> Option D

4. Quick Check:

   Heapify logic correct and complete [OK]

Hint: Heapify swaps and recurses only if needed [OK]

Common Mistakes:

• Thinking explicit base case needed for recursion
• Miscomputing child indices
• Swapping unconditionally without checking largest

5. You have a min-heap represented as an array: [5, 10, 15, 20, 25, 30]. You want to replace the root with 22 and restore the min-heap property. What will be the resulting array after heapifying?

hard

A. [10, 20, 15, 30, 25, 22]

B. [10, 20, 15, 22, 25, 30]

C. [15, 20, 22, 30, 25, 10]

D. [22, 10, 15, 20, 25, 30]

Solution

1. Step 1: Replace root with 22

   Array becomes [22, 10, 15, 20, 25, 30].

2. Step 2: Heapify down from root

   Compare 22 with children 10 and 15. 10 is smallest, swap 22 and 10: [10, 22, 15, 20, 25, 30]. Then heapify at index 1: compare 22 with children 20 and 25, 20 is smaller, swap: [10, 20, 15, 22, 25, 30]. No further swaps needed.

3. Final Answer:

   [10, 20, 15, 22, 25, 30] -> Option B

4. Quick Check:

   Replace root, bubble down to restore min-heap [OK]

Hint: Replace root, swap with smaller child until heap restored [OK]

Common Mistakes:

• Swapping with larger child instead of smaller
• Not continuing heapify after first swap
• Confusing min-heap with max-heap rules