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

Recall & Review

beginner

What is the main goal of the 'Build Heap from Array Heapify' process?

To rearrange the elements of an unsorted array so that it satisfies the heap property, making it a valid heap (usually a max-heap or min-heap).

beginner

In the heapify process, from which index do we start to build the heap from an array?

We start from the last non-leaf node, which is at index (n/2 - 1) where n is the number of elements in the array, and move upwards to the root.

intermediate

What does the 'heapify' function do at a given node in the array?

It ensures the subtree rooted at that node satisfies the heap property by comparing the node with its children and swapping if necessary, then recursively heapifying the affected subtree.

advanced

Why is the Build Heap operation efficient with O(n) time complexity instead of O(n log n)?

Because heapify is called on nodes starting from the bottom, and lower levels have many nodes but small height, so the total work sums up to O(n), not O(n log n).

intermediate

What is the difference between 'heapify' and 'build heap'?

'Heapify' fixes the heap property at a single node and its subtree, while 'build heap' applies heapify starting from the last non-leaf node up to the root to build a heap from the entire array.

Where do you start heapifying when building a heap from an array?

A From the middle node (n/2)

B From the root node (index 0)

C From the last leaf node (n - 1)

D From the last non-leaf node (n/2 - 1)

Heapify starts from the last non-leaf node because leaf nodes are already heaps by definition.

What property does a max-heap satisfy?

A Parent node is larger than children

B Parent node is smaller than children

C All nodes have equal values

D Children nodes are larger than parent

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

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

A O(n)

B O(n^2)

C O(n log n)

D O(log n)

Building a heap from an array using heapify runs in O(n) time due to the efficient bottom-up approach.

What happens if the heap property is violated at a node during heapify?

A The node is removed

B The node is swapped with the largest (or smallest) child and heapify continues recursively

C The heap is rebuilt from scratch

D Nothing, heapify stops

Heapify swaps the node with the appropriate child and continues to fix the subtree.

Which data structure is typically represented as an array when using heapify?

A Stack

B Linked list

C Binary heap

D Queue

Binary heaps are commonly represented as arrays for efficient indexing and heapify operations.

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

Think about fixing smaller heaps from bottom to top.

Why is the build heap operation more efficient than repeatedly inserting elements into a heap?

Consider the difference in how heap property is restored.

Practice

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

easy

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

B. To sort the array in ascending order

C. To find the maximum element in the array

D. To reverse the array elements

Solution

1. Step 1: Understand heap property

   A heap must satisfy the heap property where each parent node is greater (max-heap) or smaller (min-heap) than its children.

2. Step 2: Role of heapify

   The heapify process rearranges elements to ensure this property holds for every subtree starting from a node.

3. Final Answer:

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

4. Quick Check:

   Heapify = Rearrange for heap property [OK]

Hint: Heapify fixes subtree to maintain heap order [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 the Heapify method in C# for an array arr of size n at index i?

easy

A. Heapify(arr, n, i);

B. Heapify(i, arr, n);

C. Heapify(n, i, arr);

D. Heapify(arr, i, n);

Solution

1. Step 1: Check method signature

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

2. Step 2: Match parameters order

   Heapify(arr, n, i); matches the correct order: array, size, index.

3. Final Answer:

   Heapify(arr, n, i); -> Option A

4. Quick Check:

   Heapify(arr, n, i) correct call [OK]

Hint: Remember parameter order: array, size, index [OK]

Common Mistakes:

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

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

medium

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

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

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

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

Solution

1. Step 1: Identify node at index 1

   Value is 10, children at indices 3 (5) and 4 (1).

2. Step 2: Check heap property

   10 is greater than both children, so no swaps needed.

3. Final Answer:

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

4. Quick Check:

   Parent 10 > children 5,1 so unchanged [OK]

Hint: Check parent vs children values before swapping [OK]

Common Mistakes:

• Swapping when parent is already largest
• Confusing indices of children
• Assuming heapify sorts entire array

4. Consider this code snippet for heapify in C#:

void Heapify(int[] arr, int n, int i) {
  int largest = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest])
    largest = left;
  if (right < n && arr[right] > arr[largest])
    largest = right;

  if (largest != i) {
    int temp = arr[i];
    arr[i] = arr[largest];
    arr[largest] = temp;
    Heapify(arr, n, largest);
  }
}

What is the bug if the recursive call is missing?

medium

A. Stack overflow error will occur

B. Array will be sorted incorrectly

C. No bug, code works fine

D. Heap property may not be restored in subtrees

Solution

1. Step 1: Understand recursive call role

   After swapping, heapify must be called on the affected child subtree to fix heap property there.

2. Step 2: Effect of missing recursion

   Without recursion, only the root node is fixed, subtrees may remain invalid heaps.

3. Final Answer:

   Heap property may not be restored in subtrees -> Option D

4. Quick Check:

   Missing recursion breaks heap property below swapped node [OK]

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

Common Mistakes:

• Assuming one swap fixes entire heap
• Thinking missing recursion causes crash
• Ignoring subtree heap violations

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

hard

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

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

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

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

Solution

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

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

2. Step 2: Heapify at index 1 (value 9)

   Children 1 (index 3), 4 (index 4). 9 is largest, no change -> [3,9,5,1,4,2]

3. Step 3: Heapify at index 0 (value 3)

   Children 9 (index 1), 5 (index 2). Largest is 9, swap 3 and 9 -> [9,3,5,1,4,2]. Now heapify at index 1 (value 3): children 1 and 4. Largest is 4, swap 3 and 4 -> [9,4,5,1,3,2]

4. Final Answer:

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

5. Quick Check:

   Bottom-up heapify gives max-heap [OK]

Hint: Heapify bottom-up from last non-leaf node [OK]

Common Mistakes:

• Not heapifying all non-leaf nodes
• Swapping incorrectly with children
• Stopping heapify too early