Heap Concept Structure and Properties in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to get the index of the left child in a heap array.

DSA C

int leftChildIndex = 2 * parentIndex [1] 1;

Drag options to blanks, or click blank then click option'

A*

B+

C-

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction instead of addition.

Using division or multiplication incorrectly.

The left child of a node at index parentIndex in a heap is at 2 * parentIndex + 1.

2fill in blank

medium

Complete the code to find the parent index of a node in a heap array.

DSA C

int parentIndex = (childIndex [1] 1) / 2;

Drag options to blanks, or click blank then click option'

A+

B/

C*

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Adding 1 instead of subtracting 1.

Using multiplication or division incorrectly.

The parent of a node at childIndex is at (childIndex - 1) / 2 in a zero-based heap array.

3fill in blank

hard

Fix the error in the code that checks if a heap property is violated between parent and child.

DSA C

if (heap[parentIndex] [1] heap[childIndex]) {
    // swap to maintain heap property
}

Drag options to blanks, or click blank then click option'

A==

B>

C<

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using greater than operator which is for min-heap.

Using equality or inequality operators incorrectly.

In a max-heap, the parent's value should be greater than the child's. We swap if heap[parentIndex] < heap[childIndex].

4fill in blank

hard

Fill both blanks to complete the code that inserts a new element into a max-heap and restores the heap property.

DSA C

heap[index] = newValue;
while (index [1] 0 && heap[parentIndex] [2] heap[index]) {
    swap(&heap[parentIndex], &heap[index]);
    index = parentIndex;
    parentIndex = (index - 1) / 2;
}

Drag options to blanks, or click blank then click option'

A>

B<

C>=

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong comparison operators causing infinite loops.

Not checking if index is greater than zero.

The loop continues while index > 0 and the parent's value is less than the current node's value, to maintain max-heap property.

5fill in blank

hard

Fill all three blanks to complete the code that builds a max-heap from an unsorted array.

DSA C

for (int i = (size / 2) - 1; i >= 0; i--) {
    heapify(heap, size, [1]);
}

void heapify(int heap[], int size, int root) {
    int largest = root;
    int left = 2 * root + [2];
    int right = 2 * root + [3];

    if (left < size && heap[left] > heap[largest])
        largest = left;
    if (right < size && heap[right] > heap[largest])
        largest = right;

    if (largest != root) {
        swap(&heap[root], &heap[largest]);
        heapify(heap, size, largest);
    }
}

Drag options to blanks, or click blank then click option'

Ai

B0

C1

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong indices for children.

Calling heapify with wrong root index.

The heapify function is called with i as root. Left child index is 2 * root + 1 and right child index is 2 * root + 2.

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