Heapify operation in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to identify the parent index in a heap array.

Data Structures Theory

parent_index = (child_index - 1) [1] 2

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

A//

B+

C*

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using normal division '/' which gives a float.

Using addition or multiplication instead of division.

In a heap represented as an array, the parent index of a child at index child_index is calculated by integer division of (child_index - 1) by 2.

2fill in blank

medium

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

Data Structures Theory

left_child_index = [1] * 2 + 1

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

Anode

Bchild_index

Cindex

Dparent_index

Attempts:

3 left

💡 Hint

Common Mistakes

Using child_index instead of parent_index.

Forgetting to add 1 after multiplication.

The left child of a node at parent_index in a heap array is at 2 * parent_index + 1.

3fill in blank

hard

Fix the error in the heapify function to correctly swap elements when the child is greater than the parent.

Data Structures Theory

if heap[[1]] > heap[parent]:
    heap[[1]], heap[parent] = heap[parent], heap[[1]]

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

Aindex

Bparent

Cchild

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Using parent index instead of child index for comparison.

Swapping the wrong elements.

To maintain the heap property, we compare the child node's value with the parent's. If the child is greater, we swap the child and parent. So, the index to check is the child's.

4fill in blank

hard

Fill both blanks to complete the heapify condition that checks if the left child exists and is greater than the parent.

Data Structures Theory

if [1] < len(heap) and heap[[2]] > heap[parent]:

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

Aleft_child_index

Bright_child_index

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Using right_child_index instead of left_child_index.

Comparing with parent index instead of child index.

The condition first checks if the left child index is within the heap size, then compares the left child's value with the parent's value.

5fill in blank

hard

Fill all three blanks to complete the dictionary comprehension that maps each node to its heapified value if it is greater than zero.

Data Structures Theory

heapified = [1]: [2] for [1], [2] in enumerate(heap) if [2] > 0}

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

Aindex

Bvalue

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same variable name for both index and value.

Not matching variable names consistently.

This comprehension creates a dictionary where each index maps to its value from the heap, but only includes values greater than zero.

Practice

1. What is the main purpose of the heapify operation in a heap data structure?

easy

A. To fix the heap property at a given node by comparing and swapping with its children

B. To insert a new element at the end of the heap

C. To delete the root element of the heap

D. To sort all elements in the heap in ascending order

Solution

1. Step 1: Understand the heap property

   The heap property requires that each parent node is ordered with respect to its children (max-heap or min-heap).

2. Step 2: Role of heapify

   Heapify fixes the heap property at a specific node by comparing it with its children and swapping if needed to maintain the heap structure.

3. Final Answer:

   To fix the heap property at a given node by comparing and swapping with its children -> Option A

4. Quick Check:

   Heapify fixes heap property locally = A [OK]

Hint: Heapify fixes heap property at one node only [OK]

Common Mistakes:

• Confusing heapify with insertion or deletion
• Thinking heapify sorts the entire heap
• Assuming heapify adds or removes elements

2. Which of the following is the correct way to call heapify on a node at index i in an array arr representing a heap of size n?

easy

A. heapify(arr, i)

B. heapify(i, arr, n)

C. heapify(n, i, arr)

D. heapify(arr, n, i)

Solution

1. Step 1: Understand heapify parameters

   Heapify usually takes the array, the size of the heap, and the index of the node to fix.

2. Step 2: Match correct parameter order

   The common order is heapify(array, size, index), so heapify(arr, n, i) is correct.

3. Final Answer:

   heapify(arr, n, i) -> Option D

4. Quick Check:

   heapify(arr, size, index) = D [OK]

Hint: Remember heapify(arr, size, index) parameter order [OK]

Common Mistakes:

• Mixing order of parameters
• Omitting the size parameter
• Passing index before array

3. Given the array [3, 9, 2, 1, 4, 5] representing a binary heap, what will be the array after calling heapify(arr, 6, 0) assuming a max-heap?

medium

A. [9, 4, 2, 1, 3, 5]

B. [9, 3, 5, 1, 4, 2]

C. [5, 9, 3, 1, 4, 2]

D. [3, 9, 2, 1, 4, 5]

Solution

1. Step 1: Identify children of node at index 0

   Index 0 has children at indices 1 (9) and 2 (2).

2. Step 2: Compare and swap to maintain max-heap

   9 is largest child, swap 3 and 9. Now at index 1, check children 3 and 4; 4 is largest, swap 3 and 4. Resulting array: [9, 4, 2, 1, 3, 5].

3. Step 3: Verify heap property

   After swaps, the array is [9, 4, 2, 1, 3, 5]. However, the [9, 3, 5, 1, 4, 2] is [9, 3, 5, 1, 4, 2], which is incorrect because 5 is at index 2, which is less than 9 but greater than 2.

4. Correction:

   Actually, the correct heapify result is [9, 4, 5, 1, 3, 2]. But this option is not present. Let's simulate carefully:
5. Start: [3,9,2,1,4,5]
6. Swap 3 and 9: [9,3,2,1,4,5]
7. Now heapify at index 1:
8. Children: index 3 (1), index 4 (4)
9. Largest child is 4 at index 4, swap 3 and 4: [9,4,2,1,3,5]
10. Heapify at index 4: children indices 9 and 10 (out of range), stop.
11. Final array: [9,4,2,1,3,5]
12. This matches [9, 4, 2, 1, 3, 5].

13. Final Answer:

    [9, 4, 2, 1, 3, 5] -> Option A

14. Quick Check:

    Heapify swaps to max child = B [OK]

Hint: Swap with largest child repeatedly for max-heap [OK]

Common Mistakes:

• Swapping with wrong child
• Not continuing heapify after first swap
• Confusing min-heap with max-heap

4. Consider this code snippet for heapify on a max-heap:

def heapify(arr, n, i):
    largest = i
    left = 2*i + 1
    right = 2*i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

What is the error if the recursive call is missing?

medium

A. The array will be sorted incorrectly

B. Heap property may not be fixed completely below the swapped node

C. The function will cause infinite recursion

D. No error, heapify works fine without recursion

Solution

1. Step 1: Understand heapify recursion role

   After swapping, heapify must fix the subtree rooted at the swapped child.

2. Step 2: Effect of missing recursion

   Without recursive call, only the current node is fixed; subtree below may violate heap property.

3. Final Answer:

   Heap property may not be fixed completely below the swapped node -> Option B

4. Quick Check:

   Missing recursion breaks full heap fix = C [OK]

Hint: Always recurse after swap to fix subtree [OK]

Common Mistakes:

• Assuming one swap fixes entire heap
• Thinking recursion causes infinite loop
• Ignoring subtree violations

5. You have an unsorted array [4, 10, 3, 5, 1]. To build a max-heap using heapify, which index should you start heapifying from and why?

hard

A. Index 4, because heapify starts from the last element

B. Index 0, because heapify must start from the root

C. Index 1, because heapify starts from the last non-leaf node upwards

D. Index 2, because heapify starts from the middle element

Solution

1. Step 1: Identify last non-leaf node

   For array size 5, last non-leaf node is at index floor(n/2)-1 = 1.

2. Step 2: Reason heapify build process

   Heapify is applied from last non-leaf node upwards to root to build heap efficiently.

3. Final Answer:

   Index 1, because heapify starts from the last non-leaf node upwards -> Option C

4. Quick Check:

   Build heap starts at last non-leaf node = A [OK]

Hint: Start heapify at last non-leaf node (floor(n/2)-1) [OK]

Common Mistakes:

• Starting heapify at root only
• Starting at last element (leaf)
• Not knowing leaf vs non-leaf nodes