Heap Concept Structure and Properties in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this min-heap insertion sequence?

Consider an empty min-heap. Insert the elements in this order: 10, 4, 15, 20, 0. What is the heap array after all insertions?

DSA C

Insert 10
Insert 4
Insert 15
Insert 20
Insert 0
Print heap array

A [0, 4, 15, 20, 10]

B [0, 10, 15, 20, 4]

C [4, 0, 15, 20, 10]

D [10, 4, 15, 20, 0]

💡 Hint

Remember min-heap keeps smallest element at root and maintains heap property after each insertion.

After inserting 10, heap is [10]. Insert 4, swap with 10 → [4,10]. Insert 15 → [4,10,15]. Insert 20 → [4,10,15,20]. Insert 0, bubble up to root → [0,4,15,20,10].

🧠 Conceptual

intermediate

Which property must a max-heap always satisfy?

Choose the correct property that a max-heap must always satisfy.

A The tree is a complete binary tree but no order property is required.

B Every leaf node is smaller than its parent.

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

D Every child node is greater than its parent.

💡 Hint

Think about what 'max' means in max-heap.

In a max-heap, each parent node must be greater than or equal to its children to keep the maximum element at the root.

🔧 Debug

advanced

What error occurs when trying to insert into a full fixed-size heap array?

Given a fixed-size array representing a heap with capacity 5, what happens if you try to insert a 6th element?

DSA C

int heap[5];
int size = 5; // heap is full
insert(heap, size, 10);

A NullPointerException or segmentation fault

B Heap property violation error

C No error, element is inserted successfully

D ArrayIndexOutOfBoundsException or equivalent error

💡 Hint

Think about what happens when you access beyond array limits.

Trying to insert beyond the fixed array size causes an out-of-bounds error because the array cannot hold more elements.

❓ Predict Output

advanced

What is the heap array after extracting the root from this max-heap?

Given max-heap array: [20, 15, 18, 8, 10, 5]. After extracting the root (20), what is the resulting heap array?

DSA C

Extract root from max-heap [20, 15, 18, 8, 10, 5]
Reheapify

A [18, 15, 5, 8, 10]

B [18, 15, 10, 8, 5]

C [15, 10, 18, 8, 5]

D [15, 18, 10, 8, 5]

💡 Hint

After removing root, replace with last element and heapify down.

Remove 20, replace root with 5 → [5,15,18,8,10]. Heapify down swaps 5 with 18 → [18,15,5,8,10]. 5 now has no children, so heapify stops.

🧠 Conceptual

expert

What is the time complexity of building a heap from an unsorted array of n elements?

Choose the correct time complexity for building a heap from an unsorted array of size n.

A O(n log n)

B O(n)

C O(log n)

D O(n^2)

💡 Hint

Heapify process is more efficient than inserting elements one by one.

Building a heap using the bottom-up heapify method runs in linear time O(n), not O(n log n).

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