Heapify operation in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the heapify operation in a heap data structure?

Heapify is the process of rearranging elements in a binary tree to satisfy the heap property, where each parent node is either greater than or equal to (max-heap) or less than or equal to (min-heap) its children.

beginner

Why is heapify important in building a heap?

Heapify ensures that the tree maintains the heap property after insertion or deletion, which is essential for efficient operations like finding the maximum or minimum element quickly.

intermediate

What is the time complexity of the heapify operation on a node?

The time complexity of heapify on a single node is O(log n), where n is the number of nodes in the heap, because it may need to move down the tree height to restore the heap property.

intermediate

How does heapify differ when building a heap from an unordered array versus after inserting a single element?

When building a heap from an unordered array, heapify is applied bottom-up starting from the last non-leaf node, while after inserting a single element, heapify is applied bottom-up (also called 'sift-up') to restore the heap property only along the path of the inserted element.

beginner

What is the difference between max-heapify and min-heapify?

Max-heapify ensures each parent node is greater than or equal to its children, while min-heapify ensures each parent node is less than or equal to its children. Both maintain the heap property but for different heap types.

What does the heapify operation do in a heap?

A Deletes the root node

B Restores the heap property by rearranging nodes

C Searches for an element

D Sorts the entire array

Heapify rearranges nodes to maintain the heap property after changes.

What is the time complexity of heapify on a node in a heap of size n?

A O(1)

B O(n)

C O(log n)

D O(n log n)

Heapify may move down the height of the tree, which is log n.

When building a heap from an unordered array, heapify is applied starting from:

A The last non-leaf node upwards

B The last leaf node

C The root node

D Random nodes

Heapify starts from the last non-leaf node and moves upward to build the heap.

In a max-heap, heapify ensures that:

A Parent nodes are smaller than children

B The heap is sorted

C All nodes have equal values

D Parent nodes are greater than or equal to children

Max-heap property requires parents to be greater than or equal to their children.

Which of the following is NOT a use of heapify?

A Searching for an element in the heap

B Building a heap from an array

C Maintaining heap property after insertion

D Restoring heap after deletion

Heapify does not perform search operations.

Explain the heapify operation and why it is important in maintaining a heap.

Think about how heapify keeps the heap organized after changes.

Describe the difference between max-heapify and min-heapify.

Consider how parent and child nodes compare in each heap type.

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