Heap Concept Structure and Properties in DSA Typescript - Build from Scratch

Heap Concept Structure and Properties

📖 Scenario: You are working on a task to organize a list of numbers so that the largest number is always easy to find. This is useful in many real-life situations like managing priorities in a to-do list or scheduling tasks.

🎯 Goal: You will build a simple max heap structure using an array in TypeScript. You will learn how to set up the heap, understand its properties, and see how the numbers are arranged.

📋 What You'll Learn

Create an array called heap with specific numbers

Create a variable heapSize to store the number of elements in the heap

Write a function isMaxHeap to check if the array satisfies max heap properties

Print the heap array and the result of isMaxHeap function

💡 Why This Matters

🌍 Real World

Heaps are used in priority queues, scheduling algorithms, and for efficient sorting methods like heapsort.

💼 Career

Understanding heaps helps in roles involving algorithm design, system optimization, and software development where priority management is needed.

1

Create the initial heap array

Create an array called heap with these exact numbers in this order: 90, 15, 10, 7, 12, 2, 7, 3

DSA Typescript

// Create the heap array with the given numbers
// Your code here

Hint

Use const heap: number[] = [...] to create the array with the exact numbers.

2

Add heap size variable

Create a variable called heapSize and set it to the length of the heap array

DSA Typescript

const heap: number[] = [90, 15, 10, 7, 12, 2, 7, 3];
// Create heapSize variable to store the number of elements
// Your code here

Hint

Use const heapSize: number = heap.length; to get the number of elements.

3

Write a function to check max heap property

Write a function called isMaxHeap that takes heap and heapSize as parameters and returns true if every parent node is greater than or equal to its children, otherwise false. Use a for loop with variable i from 0 to Math.floor(heapSize / 2) - 1 to check each parent node.

DSA Typescript

const heap: number[] = [90, 15, 10, 7, 12, 2, 7, 3];
const heapSize: number = heap.length;
// Write isMaxHeap function to check max heap property
// Your code here

Hint

Check each parent node against its left and right children using their indices.

4

Print the heap and check result

Print the heap array and then print the result of calling isMaxHeap(heap, heapSize)

DSA Typescript

const heap: number[] = [90, 15, 10, 7, 12, 2, 7, 3];
const heapSize: number = heap.length;

function isMaxHeap(heap: number[], heapSize: number): boolean {
    for (let i = 0; i <= Math.floor(heapSize / 2) - 1; i++) {
        const left = 2 * i + 1;
        const right = 2 * i + 2;

        if (left < heapSize && heap[i] < heap[left]) {
            return false;
        }
        if (right < heapSize && heap[i] < heap[right]) {
            return false;
        }
    }
    return true;
}

// Print the heap array and the result of isMaxHeap
// Your code here

Hint

Use console.log(heap); and console.log(isMaxHeap(heap, heapSize)); to print the results.

Practice

1. What is a key property of a max-heap data structure?

easy

A. Every parent node is greater than or equal to its children

B. Every parent node is less than or equal to its children

C. All leaf nodes have the same value

D. The heap is always a complete binary tree with sorted leaves

Solution

1. Step 1: Understand max-heap property

   A max-heap requires each parent node to be greater than or equal to its children to maintain the heap order.

2. Step 2: Compare options with definition

   Every parent node is greater than or equal to its children matches the max-heap property exactly, while others describe min-heap or incorrect properties.

3. Final Answer:

   Every parent node is greater than or equal to its children -> Option A

4. Quick Check:

   Max-heap property = Every parent ≥ children [OK]

Hint: Max-heap means parent ≥ children always [OK]

Common Mistakes:

• Confusing max-heap with min-heap property
• Thinking leaves must be sorted
• Assuming all leaf nodes have same value

2. Which of the following is the correct TypeScript syntax to declare a min-heap using an array?

easy

A. let minHeap = new Heap();

B. const minHeap: number[] = [];

C. const minHeap: Heap = new Heap();

D. var minHeap = [];

Solution

1. Step 1: Identify array declaration syntax in TypeScript

   Declaring an array of numbers uses syntax like const arr: number[] = [];.

2. Step 2: Check options for correct array declaration

   const minHeap: number[] = []; correctly declares an empty number array for min-heap storage. Others either use undefined Heap class or older syntax.

3. Final Answer:

   const minHeap: number[] = []; -> Option B

4. Quick Check:

   Array declaration with type = const arr: number[] = [] [OK]

Hint: Use const name: type[] = [] for array declaration [OK]

Common Mistakes:

• Using undefined Heap class without import
• Using var instead of const or let
• Missing type annotation in TypeScript

3. Given the following TypeScript code for a max-heap array representation:

const heap = [50, 30, 40, 10, 20];
console.log(heap[1]);

What will be the output?

medium

A. 10

B. 50

C. 40

D. 30

Solution

1. Step 1: Understand zero-based indexing in arrays

   Arrays in TypeScript start at index 0, so heap[0] = 50, heap[1] = 30.

2. Step 2: Identify value at index 1

   heap[1] accesses the second element, which is 30.

3. Final Answer:

   30 -> Option D

4. Quick Check:

   heap[1] = 30 [OK]

Hint: Array index starts at 0, so heap[1] is second element [OK]

Common Mistakes:

• Assuming heap indexing starts at 1
• Confusing value at index 0 with index 1
• Mixing up max-heap property with array indexing

4. Consider this TypeScript snippet to insert a value into a max-heap array:

const heap = [40, 30, 20];
heap.push(50);
// Missing code here to maintain heap property
console.log(heap);

Which code snippet correctly restores the max-heap property after insertion?

medium

A. heap.sort((a, b) => a - b);

B. while (index > 0 && heap[parent(index)] > heap[index]) { swap(heap, parent(index), index); index = parent(index); }

C. while (index > 0 && heap[parent(index)] < heap[index]) { swap(heap, parent(index), index); index = parent(index); }

D. heap.reverse();

Solution

1. Step 1: Understand heapify-up process for max-heap

   After insertion, we compare the inserted node with its parent and swap if child is greater, repeating until heap property is restored.

2. Step 2: Analyze code snippets

   while (index > 0 && heap[parent(index)] < heap[index]) { swap(heap, parent(index), index); index = parent(index); } correctly uses a while loop to swap child and parent if child is greater. while (index > 0 && heap[parent(index)] > heap[index]) { swap(heap, parent(index), index); index = parent(index); } reverses condition (wrong for max-heap). Options A, B, and D do not maintain heap structure.

3. Final Answer:

   while (index > 0 && heap[parent(index)] < heap[index]) { swap(heap, parent(index), index); index = parent(index); } -> Option C

4. Quick Check:

   Heapify-up swaps if child > parent [OK]

Hint: Swap up while child > parent to fix max-heap [OK]

Common Mistakes:

• Using wrong comparison direction in heapify-up
• Sorting array instead of heapifying
• Reversing array instead of fixing heap

5. You have a min-heap represented as an array: [5, 10, 15, 20, 25]. You want to insert 12 and maintain the min-heap property. Which sequence of array states correctly shows the heap after insertion and heapify-up?

hard

A. [5, 10, 15, 20, 25, 12] -> [5, 10, 12, 20, 25, 15]

B. [5, 10, 15, 20, 25, 12] -> [5, 10, 15, 20, 25, 12]

C. [5, 10, 15, 20, 25, 12] -> [5, 12, 15, 20, 25, 10]

D. [5, 10, 15, 20, 25, 12] -> [12, 5, 15, 20, 25, 10]

Solution

1. Step 1: Insert 12 at the end of the array

   Initial array after insertion: [5, 10, 15, 20, 25, 12]

2. Step 2: Heapify-up to maintain min-heap

   Compare 12 with its parent 15 (index 2). Since 12 < 15, swap them. New array: [5, 10, 12, 20, 25, 15]. No further swaps needed as 12 > 10.

3. Final Answer:

   [5, 10, 15, 20, 25, 12] -> [5, 10, 12, 20, 25, 15] -> Option A

4. Quick Check:

   Heapify-up swaps child < parent in min-heap [OK]

Hint: Swap inserted value up while smaller than parent in min-heap [OK]

Common Mistakes:

• Not swapping inserted value with parent when smaller
• Assuming no change after insertion
• Swapping with wrong parent index