Build Heap from Array Heapify in DSA Typescript - Build from Scratch

Build Heap from Array Heapify

📖 Scenario: You have a list of numbers representing tasks with different priorities. You want to organize them so the highest priority task is always easy to find. This is like arranging a pile of books so the biggest book is always on top.

🎯 Goal: Build a max heap from an unsorted array using the heapify process. This means rearranging the array so each parent number is bigger than its children.

📋 What You'll Learn

Create an array called tasks with the exact numbers: 4, 10, 3, 5, 1

Create a variable called n to store the length of the array

Write a heapify function that takes the array, size n, and an index i to maintain the max heap property

Use a for loop to build the heap from the bottom up

Print the final heap array after building it

💡 Why This Matters

🌍 Real World

Heaps are used in task scheduling, priority queues, and efficient sorting algorithms.

💼 Career

Understanding heaps helps in software roles involving data processing, optimization, and system design.

1

Create the initial array

Create an array called tasks with these exact numbers: 4, 10, 3, 5, 1.

DSA Typescript

const tasks = [4, 10, 3, 5, 1];
// Your code here

Hint

Use square brackets [] to create the array and separate numbers with commas.

2

Create a variable for array length

Create a variable called n and set it to the length of the tasks array.

DSA Typescript

const tasks = [4, 10, 3, 5, 1];
const n = tasks.length;
// Your code here

Hint

Use array.length to get the number of items in the array.

3

Write the heapify function and build the heap

Write a function called heapify that takes parameters arr, n, and i. Inside, find the largest among i, left child 2*i + 1, and right child 2*i + 2. Swap if needed and call heapify recursively. Then, use a for loop starting from Math.floor(n / 2) - 1 down to 0 to build the heap by calling heapify(tasks, n, i).

DSA Typescript

const tasks = [4, 10, 3, 5, 1];
const n = tasks.length;

function heapify(arr: number[], n: number, i: number): void {
    // Your code here
}

for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    // Your code here
}

Hint

Remember to check if left and right children are inside the array before comparing. Swap and call heapify again if you change the root.

4

Print the heap array

Print the tasks array after building the heap using console.log(tasks).

DSA Typescript

const tasks = [4, 10, 3, 5, 1];
const n = tasks.length;

function heapify(arr: number[], n: number, i: number): void {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

    if (left  arr[largest]) {
        largest = left;
    }

    if (right  arr[largest]) {
        largest = right;
    }

    if (largest !== i) {
        const temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        heapify(arr, n, largest);
    }
}

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

// Print the tasks array
// Your code here

Hint

Use console.log(tasks) to show the final heap array.

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