Heap Insert Operation Bubble Up in DSA Typescript - Build from Scratch

Heap Insert Operation Bubble Up

📖 Scenario: You are managing a priority queue using a min-heap. A min-heap is a special tree where the smallest number is always at the top. When you add a new number, you need to place it correctly so the smallest number stays on top.Imagine you have a list of tasks with different priorities. You want to add a new task and keep the list ordered by priority.

🎯 Goal: Build a min-heap insert operation that adds a new number to the heap and moves it up (bubble up) to keep the smallest number at the top.

📋 What You'll Learn

Create an array called heap with initial values representing a min-heap

Create a variable called newValue to hold the number to insert

Write a function called bubbleUp that moves the last element up to keep the min-heap property

Print the heap array after insertion and bubbling up

💡 Why This Matters

🌍 Real World

Heaps are used in task scheduling, priority queues, and algorithms like Dijkstra's shortest path.

💼 Career

Understanding heap insertions is important for software engineers working with efficient data structures and algorithms.

1

Create the initial min-heap array

Create an array called heap with these exact numbers in order: [10, 15, 20, 17, 25]

DSA Typescript

# Create the initial heap array
# Your code here

Hint

Use const heap = [10, 15, 20, 17, 25]; to create the array.

2

Add the new value to insert

Create a variable called newValue and set it to 8. Then add newValue to the end of the heap array using push.

DSA Typescript

const heap = [10, 15, 20, 17, 25];
# Create newValue = 8 and push it to heap
# Your code here

Hint

Use const newValue = 8; and heap.push(newValue);.

3

Write the bubbleUp function to restore min-heap

Write a function called bubbleUp that takes no arguments. It should start from the last index of heap and swap the element with its parent while it is smaller than the parent. Use a while loop and calculate the parent index as Math.floor((index - 1) / 2). Stop when the element is not smaller than the parent or when it reaches the root (index 0).

DSA Typescript

const heap = [10, 15, 20, 17, 25];
const newValue = 8;
heap.push(newValue);

# Write bubbleUp function to move last element up
# Your code here

Hint

Use a while loop and swap elements if the child is smaller than the parent.

4

Call bubbleUp and print the heap

Call the bubbleUp() function. Then print the heap array using console.log(heap).

DSA Typescript

const heap = [10, 15, 20, 17, 25];
const newValue = 8;
heap.push(newValue);

function bubbleUp() {
    let index = heap.length - 1;
    while (index > 0) {
        let parentIndex = Math.floor((index - 1) / 2);
        if (heap[index] < heap[parentIndex]) {
            // Swap
            [heap[index], heap[parentIndex]] = [heap[parentIndex], heap[index]];
            index = parentIndex;
        } else {
            break;
        }
    }
}

# Call bubbleUp and print heap
# Your code here

Hint

Call bubbleUp() and then console.log(heap).