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

Recall & Review

beginner

What is the main 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 is the formula to find the left child index of a node at index i?

Left child index = 2 * i + 1

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 are heapified bottom-up efficiently.

intermediate

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

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 max-heap, heapify ensures parent nodes are greater than children. In min-heap, heapify ensures parent nodes are smaller than children.

What is the index of the last non-leaf node in a zero-based array of size n?

A Math.floor(n / 2) - 1

B n - 1

C Math.floor(n / 2)

D 0

The last non-leaf node is at index Math.floor(n / 2) - 1 because nodes after this index are leaves.

Which of the following best describes the heapify operation?

A Inserting a new element at the end

B Swapping elements to maintain heap property starting from a node downwards

C Sorting the entire array

D Removing the root element

Heapify fixes the heap property by swapping elements from a node down to its children.

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

A O(n)

B O(n log n)

C O(1)

D O(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 heap from an array, why is the overall time complexity O(n) and not O(n log n)?

A Because heapify is called fewer times on nodes near the bottom which have smaller heights

B Because the array is already sorted

C Because heapify is a constant time operation

D Because only half the elements are heapified

Nodes near the bottom have smaller heights, so heapify takes less time on them, making total time O(n).

In a max-heap, after heapify, what can be said about the root node?

A It is the median element

B It is the smallest element in the heap

C It is the largest element in the heap

D It is the last inserted element

In a max-heap, the root node is always the largest element after heapify.

Describe step-by-step how to build a max-heap from an unsorted array using heapify.

Think about fixing the heap property from bottom to top.

Explain why heapify is more efficient when building a heap from an array compared to inserting elements one by one.

Compare bulk heap construction vs repeated insertions.

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 parent nodes follow a specific order compared to children (max-heap or min-heap).

2. Step 2: Role of heapify

   Heapify rearranges elements so that 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 order to build a valid heap 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 TypeScript syntax to start heapifying from the last non-leaf node in an array arr of length n?

easy

A. for(let i = Math.floor(n / 2); i < n; i++) { heapify(arr, n, i); }

B. for(let i = Math.floor(n / 2) - 1; i >= 0; i--) { heapify(arr, n, i); }

C. for(let i = n - 1; i >= 0; i--) { heapify(arr, n, i); }

D. for(let i = 0; i < n; i++) { heapify(arr, n, i); }

Solution

1. Step 1: Identify last non-leaf node index

   In a heap array, last non-leaf node is at index Math.floor(n/2) - 1.

2. Step 2: Loop from last non-leaf to root

   We heapify from this index down to 0 to ensure all subtrees satisfy heap property.

3. Final Answer:

   for(let i = Math.floor(n / 2) - 1; i >= 0; i--) { heapify(arr, n, i); } -> Option B

4. Quick Check:

   Start heapify at last non-leaf node [OK]

Hint: Start heapify at Math.floor(n/2)-1 down to 0 [OK]

Common Mistakes:

• Starting heapify from 0 upwards
• Starting heapify from last element
• Looping beyond last non-leaf node

3. Given the array arr = [3, 9, 2, 1, 4, 5], what is the array after building a max-heap using heapify?

medium

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

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

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

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

Solution

1. Step 1: Start heapify from index 2 (Math.floor(6/2)-1)

   Heapify at index 2: children 5 (index 5), swap 2 and 5 to get [3,9,5,1,4,2].

2. Step 2: Heapify at index 1 and 0

   Index 1: children 1 and 4, max is 9 at index 1, no swap. Index 0: children 9 and 5, swap 3 and 9. Final array: [9,4,5,1,3,2]

3. Final Answer:

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

4. Quick Check:

   Max-heap root is 9, children smaller [OK]

Hint: Heapify bottom-up swaps to fix max-heap [OK]

Common Mistakes:

• Not swapping correctly during heapify
• Confusing min-heap with max-heap
• Leaving original array unchanged

4. Consider this TypeScript code snippet to build a max heap:

function heapify(arr: number[], n: number, i: number) {
  let largest = i;
  let left = 2 * i + 1;
  let 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) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

function buildHeap(arr: number[]) {
  let n = arr.length;
  for (let i = 0; i <= Math.floor(n / 2); i++) {
    heapify(arr, n, i);
  }
}

What is the error in this code?

medium

A. The loop in buildHeap should run from Math.floor(n/2)-1 down to 0

B. The heapify function swaps elements incorrectly

C. The left and right child indices are calculated wrongly

D. The buildHeap function should not call heapify

Solution

1. Step 1: Analyze buildHeap loop range

   The loop runs from 0 up to Math.floor(n/2), but heapify must start from last non-leaf node down to root.

2. Step 2: Correct loop direction and range

   Loop should be: for(let i = Math.floor(n/2) - 1; i >= 0; i--) to ensure all subtrees heapify properly.

3. Final Answer:

   The loop in buildHeap should run from Math.floor(n/2)-1 down to 0 -> Option A

4. Quick Check:

   Heapify bottom-up loop direction matters [OK]

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

Common Mistakes:

• Looping heapify top-down instead of bottom-up
• Incorrect child index calculations
• Not swapping elements during heapify

5. You have an array arr = [4, 10, 3, 5, 1, 2]. After building a min-heap using heapify, what will be the array representation?

hard

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

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

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

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

Solution

1. Step 1: Build min-heap bottom-up

   Start heapify from index 2 (Math.floor(6/2)-1): heapify at index 2 swaps 3 and 2 to get [4,10,2,5,1,3].

2. Step 2: Heapify at index 1 and 0

   At index 1: children 5 and 1, swap 10 and 1 -> [4,1,2,5,10,3]. At index 0: children 1 and 2, swap 4 and 1 -> [1,4,2,5,10,3].

3. Final Answer:

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

4. Quick Check:

   Min-heap root is smallest element 1 [OK]

Hint: Min-heap root is smallest; heapify swaps bottom-up [OK]

Common Mistakes:

• Confusing min-heap with max-heap results
• Not swapping correctly during heapify
• Assuming sorted array equals heap