Heap Concept Structure and Properties in DSA C - Execution Trace

Concept Flow - Heap Concept Structure and Properties

Start with empty heap

↓

Insert element at end of array

↓

Compare with parent

↓

Swap with parent

↓

Repeat compare with new parent

↓

Heap property restored

↓

Heap ready for next operation

Shows how elements are added to the heap and moved up to maintain heap order.

Execution Sample

DSA C

Insert 8 into min-heap array [10, 15, 30, 40, 50, 100, 40]
Bubble up to restore heap property

Inserts a new element and moves it up to keep the min-heap property.

Execution Table

Step	Operation	Nodes in Heap (Array)	Pointer Changes	Visual State (Tree)
1	Start with initial heap	[10, 15, 30, 40, 50, 100, 40]	head=0	10 / \ 15 30 / \ / \ 40 50 100 40
2	Insert 8 at end	[10, 15, 30, 40, 50, 100, 40, 8]	new_node=7	10 / \ 15 30 / \ / \ 40 50 100 40 / 8
3	Compare 8 with parent 40 (index 3)	[10, 15, 30, 40, 50, 100, 40, 8]	compare indices 7 and 3	8 < 40? Yes
4	Swap 8 and 40	[10, 15, 30, 8, 50, 100, 40, 40]	swap indices 7 and 3	10 / \ 15 30 / \ / \ 8 50 100 40 / 40
5	Compare 8 with new parent 15 (index 1)	[10, 15, 30, 8, 50, 100, 40, 40]	compare indices 3 and 1	8 < 15? Yes
6	Swap 8 and 15	[10, 8, 30, 15, 50, 100, 40, 40]	swap indices 3 and 1	10 / \ 8 30 / \ / \ 15 50 100 40 / 40
7	Compare 8 with new parent 10 (index 0)	[10, 8, 30, 15, 50, 100, 40, 40]	compare indices 1 and 0	8 < 10? Yes
8	Swap 8 and 10	[8, 10, 30, 15, 50, 100, 40, 40]	swap indices 1 and 0	8 / \ 10 30 / \ / \ 15 50 100 40 / 40
9	Compare 8 with parent (none, root)	[8, 10, 30, 15, 50, 100, 40, 40]	at root, stop	Heap property restored
10	End	[8, 10, 30, 15, 50, 100, 40, 40]	no pointer changes	Final heap state

💡 Reached root node, no more parents to compare, heap property restored

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	Final
Heap Array	[10, 15, 30, 40, 50, 100, 40]	[10, 15, 30, 40, 50, 100, 40, 8]	[10, 15, 30, 8, 50, 100, 40, 40]	[10, 8, 30, 15, 50, 100, 40, 40]	[8, 10, 30, 15, 50, 100, 40, 40]	[8, 10, 30, 15, 50, 100, 40, 40]
New Node Index	N/A	7	3	1	0	N/A
Parent Index	N/A	3	1	0	N/A	N/A

Key Moments - 3 Insights

Why do we compare the new element with its parent during insertion?

Because the heap property requires parents to be smaller (min-heap) or larger (max-heap) than children. We check and swap if violated, as shown in steps 3, 5, and 7 in the execution_table.

Why does the insertion stop when the new element reaches the root?

At the root, there is no parent to compare with, so the heap property is restored. This is shown in step 9 where the comparison stops.

Why do we insert the new element at the end of the array first?

Because the heap is a complete binary tree, new nodes fill from left to right at the bottom level. Inserting at the end maintains this structure before fixing order by bubbling up.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the heap array after swapping?

A [10, 15, 30, 40, 50, 100, 40, 8]

B [8, 15, 30, 40, 50, 100, 40, 40]

C [10, 15, 30, 8, 50, 100, 40, 40]

D [10, 8, 30, 15, 50, 100, 40, 40]

💡 Hint

Check the 'Nodes in Heap (Array)' column at step 4 in execution_table

At which step does the new element become the root of the heap?

A Step 8

B Step 6

C Step 9

D Step 10

💡 Hint

Look at the 'Visual State (Tree)' column and 'Pointer Changes' in steps 7 and 8

If the inserted element was larger than its parent at step 3, what would happen?

A It would swap with the parent anyway

B Insertion would stop immediately

C It would bubble down instead

D The heap would become invalid

💡 Hint

Refer to the decision at step 3 in execution_table where 'Smaller?' leads to swap, else stop

Concept Snapshot

Heap is a complete binary tree stored as an array.
Insert new element at array end.
Compare with parent and swap if heap property violated.
Repeat until root or property restored.
Min-heap: parent ≤ children; Max-heap: parent ≥ children.
Maintains fast access to min or max element.

Full Transcript

A heap is a special tree structure where each parent node follows a specific order with its children, like being smaller in a min-heap. When we add a new element, we put it at the end of the array to keep the tree complete. Then, we compare it with its parent. If it breaks the heap rule, we swap them. We keep doing this until the new element is in the right place or it reaches the root. This process is called bubbling up. The example shows inserting 8 into a min-heap, swapping it up until it becomes the root, restoring the heap property.

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