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.