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 already satisfy the heap property, starting from the last non-leaf node ensures all subtrees become heaps 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.

Max-heap ensures each parent node is greater than its children; min-heap ensures each parent node is smaller than its children. Heapify adjusts nodes accordingly.

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

A n/3

B n - 1

C n/2

D n/2 - 1

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 Swapping elements to maintain heap property starting from a node downwards

B Sorting the entire array

C Inserting a new element into the heap

D Removing the root element

Heapify fixes the heap property by moving a node downwards if needed.

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

A O(n)

B O(1)

C O(log n)

D O(n log n)

Heapify on a single node takes O(log n) time because it may move down the height of the heap.

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

A Node is greater than or equal to its children

B Node is less than its children

C Node is equal to its children

D Node is the smallest element in the heap

In a max-heap, each parent node must be greater than or equal to its children.

Which of these is NOT a step in building a heap from an array using heapify?

A Heapify each node to maintain heap property

B Sort the array in ascending order

C Start heapifying from the last non-leaf node to the root

D Use array indices to find children nodes

Sorting the array is not part of building a heap; heapify rearranges elements to satisfy heap property.

Describe the process of building a heap from an unsorted array using heapify.

Think about fixing subtrees from bottom to top.

Explain why the build heap operation using heapify is more efficient than inserting elements one by one into an empty heap.

Compare total time complexities and approach.

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 rearrange elements to satisfy the heap property

D. To reverse the array elements

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 this property holds for every subtree starting from a node.

3. Final Answer:

   To rearrange elements to satisfy the heap property -> Option C

4. Quick Check:

   Heapify = rearrange for heap property [OK]

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

Common Mistakes:

• Thinking heapify sorts the array
• Confusing heapify with finding max 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, i, n);

C. heapify(n, i, arr);

D. heapify(arr, n, i);

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

   heapify(arr, n, i); matches the standard signature: heapify(arr, n, i); others have wrong order.

3. Final Answer:

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

4. Quick Check:

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

Hint: Remember: array, size, then index for heapify call [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, 0) assuming a max-heap?

medium

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

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

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

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

Solution

1. Step 1: Identify root and children

   Index 0 has value 4; children at indices 1 and 2 are 10 and 3.

2. Step 2: Swap with largest child and heapify

   Swap 4 with 10 (largest child). Now at index 1, value 4 has children 5 and 1. Swap 4 with 5. Final array: [10, 5, 3, 4, 1]

3. Final Answer:

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

4. Quick Check:

   Max-heap root fixed = [10, 5, 3, 4, 1] [OK]

Hint: Swap root with largest child, then heapify child subtree [OK]

Common Mistakes:

• Not swapping with largest child
• Stopping after first swap
• Confusing min-heap with max-heap

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. Heapify should be called with index i+1

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

C. Loop should run from 0 to n-1

D. No error, code is correct

Solution

1. Step 1: Understand heap building order

   Heap building requires heapify from last non-leaf node down to root, i.e., from n/2 - 1 down to 0.

2. Step 2: Identify loop direction and range error

   The loop incorrectly goes from 0 up to n/2, which is wrong direction and range.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Looping forward instead of backward
• Starting loop at 0 without decrement
• Calling heapify with wrong index

5. You have an array arr = [3, 9, 2, 1, 4, 5]. After building a max heap using the standard heapify method, what is the final array?

hard

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

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

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

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

Solution

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

   Last non-leaf index = n/2 -1 = 2. Heapify at index 2: children 5 and none, 2 < 5, swap to get [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 change.

3. Step 3: Heapify at index 0

   Index 0 value 3, children 9 and 5. Swap 3 with 9: [9,3,5,1,4,2]. Heapify at index 1: value 3, children 1 and 4. Swap 3 with 4: [9,4,5,1,3,2].

4. Final Answer:

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

5. Quick Check:

   Max heap built = [9,4,5,1,3,2] [OK]

Hint: Heapify bottom-up, swap with largest child repeatedly [OK]

Common Mistakes:

• Not heapifying all parents
• Swapping with wrong child
• Stopping heapify early