Heapify operation in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

What is the primary purpose of the heapify operation?

Choose the best description of what the heapify operation does in a binary heap.

A It removes the root element from the heap.

B It sorts all elements in ascending order.

C It rearranges elements to satisfy the heap property starting from a given node.

D It duplicates the heap structure to create a new heap.

💡 Hint

Think about how a heap maintains its special order after changes.

The heapify operation adjusts the subtree rooted at a given node to maintain the heap property, ensuring the parent node is ordered correctly relative to its children.

📋 Factual

intermediate

What is the time complexity of heapify on a subtree of size n?

Identify the time complexity of the heapify operation when applied to a subtree with n nodes.

A O(n log n)

B O(1)

C O(n)

D O(log n)

💡 Hint

Consider the height of the subtree and how many swaps heapify might perform.

Heapify works by moving down the tree levels, and since the height of a heap is log n, the time complexity is O(log n).

🔍 Analysis

advanced

What is the output array after heapifying the subtree rooted at index 1 in the array [4, 10, 3, 5, 1] (0-based index)?

Given the array representing a binary heap: [4, 10, 3, 5, 1], apply heapify at index 1 and select the resulting array.

Data Structures Theory

array = [4, 10, 3, 5, 1]
heapify at index 1

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

B 4, 10, 3, 5, 1]

C [4, 10, 3, 5, 1

D ]1 ,5 ,3 ,01 ,4[

💡 Hint

Check if the subtree rooted at index 1 already satisfies the heap property.

At index 1, the value is 10 with children 5 and 1. Since 10 is greater than both children, the subtree already satisfies the max-heap property, so the array remains unchanged.

❓ Comparison

advanced

Which option correctly describes the difference between heapify and build-heap operations?

Select the statement that best explains how heapify and build-heap differ.

A Heapify fixes the heap property at one node; build-heap applies heapify from bottom up to the entire array.

B Heapify sorts the entire array; build-heap removes the largest element.

C Heapify duplicates the heap; build-heap deletes the heap.

D Heapify inserts a new element; build-heap extracts the root.

💡 Hint

Think about the scope of each operation.

Heapify adjusts the heap property at a single node, while build-heap runs heapify on all non-leaf nodes from bottom to top to create a valid heap.

❓ Reasoning

expert

If you apply heapify on all nodes from the last non-leaf node up to the root in an array of size n, what is the overall time complexity?

Determine the total time complexity of building a heap by applying heapify from the last non-leaf node up to the root in an array of size n.

A O(n log n)

B O(n)

C O(log n)

D O(n^2)

💡 Hint

Consider that heapify takes less time on nodes lower in the tree and more time near the root.

Although heapify takes O(log n) time per node, most nodes are near the leaves and require less work. Summing all heapify calls results in O(n) total time.

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