Build Heap from Array Heapify in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the purpose of the heapify process when building a heap from an array?

Heapify rearranges elements to satisfy the heap property, ensuring each parent node is greater (max-heap) or smaller (min-heap) than its children.

beginner

In a zero-based array representation of a heap, what are the indices of the left and right children of the node at index i?

Left child index = 2 * i + 1, Right child index = 2 * i + 2.

intermediate

Why do we start heapifying from the last non-leaf node when building a heap from an array?

Because leaf nodes are already heaps, starting from the last non-leaf node ensures all subtrees satisfy the heap property efficiently.

intermediate

What is the time complexity of building a heap from an unsorted array using heapify?

The time complexity is O(n), where n is the number of elements in the array.

beginner

Explain the difference between max-heap and min-heap in the context of heapify.

In a max-heap, each parent node is greater than or equal to its children, while in a min-heap, each parent node is less than or equal to its children. Heapify adjusts nodes accordingly.

What is the index of the last non-leaf node in a heap represented by an array of size n?

A n/2 - 1

B n - 1

C n/2

D 0

The last non-leaf node is at index n/2 - 1 in zero-based indexing.

Which of the following best describes the heapify operation?

A Rearranging a subtree to satisfy the heap property

B Sorting the entire array

C Inserting a new element into the heap

D Removing the root element

Heapify fixes the heap property in a subtree rooted at a given node.

What is the time complexity of heapify on a single node in the worst case?

A O(1)

B O(n)

C O(log n)

D O(n log n)

Heapify may move down the tree height, which is log n in worst case.

When building a max-heap from an array, which property must be true after heapify is applied to a node?

A Parent node is less than its children

B Parent node is greater than or equal to its children

C Children nodes are sorted

D Array is fully sorted

Max-heap property requires parent >= children.

Why is building a heap from an array more efficient than inserting elements one by one?

A Because insertion requires no comparisons

B Because insertion is O(1)

C Because heapify sorts the array

D Because heapify runs in O(n) time, while repeated insertions take O(n log n)

Building heap with heapify is O(n), faster than O(n log n) for repeated insertions.

Describe the steps to build a max-heap from an unsorted array using heapify.

Think about fixing subtrees from bottom to top.

Explain why the time complexity of building a heap from an array is O(n) and not O(n log n).

Consider the height and number of nodes at each level.

Practice

1. What is the main purpose of the heapify process when building a heap from an array?

easy

A. To find the maximum element in the array

B. To sort the array in ascending order

C. To reverse the array elements

D. To rearrange the array elements to satisfy the heap property

Solution

1. Step 1: Understand heap property

   A heap is a special tree where each parent node is greater (max-heap) or smaller (min-heap) than its children.

2. Step 2: Role of heapify

   Heapify rearranges elements so the heap property holds for every subtree, starting from the bottom.

3. Final Answer:

   To rearrange the array elements to satisfy the heap property -> Option D

4. Quick Check:

   Heapify = Rearrange for heap property [OK]

Hint: Heapify fixes subtree order to build a heap fast [OK]

Common Mistakes:

• Thinking heapify sorts the array
• Confusing heapify with finding max/min element
• Assuming heapify reverses the array

2. Which of the following is the correct way to call heapify on an array arr of size n starting from index i in C?

easy

A. heapify(i, arr, n);

B. heapify(arr, n, i);

C. heapify(n, arr, i);

D. heapify(arr, i, n);

Solution

1. Step 1: Understand heapify parameters

   Heapify usually takes the array, its size, and the index to heapify from, in that order.

2. Step 2: Match correct syntax

   Calling heapify(arr, n, i); matches the standard parameter order: array, size, index.

3. Final Answer:

   heapify(arr, n, i); -> Option B

4. Quick Check:

   Function call order = arr, size, index [OK]

Hint: Remember: array first, then size, then index [OK]

Common Mistakes:

• Mixing parameter order
• Passing index before array
• Confusing size and index positions

3. Given the array arr = [4, 10, 3, 5, 1], what will be the array after calling heapify(arr, 5, 1) assuming a max-heap?

medium

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

B. [4, 1, 3, 5, 10]

C. [4, 10, 3, 5, 1]

D. [10, 4, 3, 5, 1]

Solution

1. Step 1: Identify children of index 1

   Index 1 has children at indices 3 and 4 with values 5 and 1.

2. Step 2: Compare and swap if needed

   Value at index 1 is 10, which is greater than both children, so no swap needed.

3. Final Answer:

   [4, 10, 3, 5, 1] -> Option C

4. Quick Check:

   Parent >= children, no change [OK]

Hint: Check parent vs children, swap only if smaller [OK]

Common Mistakes:

• Swapping when parent is already largest
• Mixing up child indices
• Assuming heapify sorts entire array

4. Consider this code snippet to build a max heap from array arr of size n. Identify the error:

for (int i = 0; i <= n/2; i++) {
    heapify(arr, n, i);
}

medium

A. Loop should start from n/2 - 1 and go down to 0

B. Loop should start from 0 and go to n - 1

C. heapify function parameters are incorrect

D. No error, code is correct

Solution

1. Step 1: Understand heap building order

   Heap building starts from last non-leaf node at index n/2 - 1 down to 0.

2. Step 2: Check loop direction and range

   Loop incorrectly goes up from 0 to n/2, should go down from n/2 - 1 to 0.

3. Final Answer:

   Loop should start from n/2 - 1 and go down to 0 -> Option A

4. Quick Check:

   Build heap loops down from n/2-1 [OK]

Hint: Build heap loops backward from last parent [OK]

Common Mistakes:

• Looping forward instead of backward
• Starting loop at 0 without going down
• Incorrect heapify parameters

5. You have the array [3, 9, 2, 1, 4, 5]. After building a max heap using heapify from the bottom up, what is the final array?

hard

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

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

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

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

Solution

1. Step 1: Start heapify from last non-leaf node

   Last non-leaf node index = n/2 - 1 = 2. Heapify at index 2: children 5 and no right child. Swap 2 and 5 -> [3,9,5,1,4,2]

2. Step 2: Heapify at index 1

   Index 1 value 9, children 1 and 4. 9 is largest, no swap -> [3,9,5,1,4,2]

3. Step 3: Heapify at index 0

   Index 0 value 3, children 9 and 5. Largest is 9 at index 1, swap -> [9,3,5,1,4,2]. Heapify at index 1 again: 3 with children 1 and 4, largest is 4 at index 4, swap -> [9,4,5,1,3,2]

4. Final Answer:

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

5. Quick Check:

   Bottom-up heapify fixes subtree order [OK]

Hint: Heapify bottom-up swaps parents with largest child [OK]

Common Mistakes:

• Not heapifying children after swap
• Swapping with wrong child
• Stopping heapify too early