Heap Concept Structure and Properties in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create an empty heap array.

DSA Typescript

const heap: number[] = [1];

Drag options to blanks, or click blank then click option'

Anull

B{}

C[]

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using {} which is an object, not an array.

Using null or 0 which are not arrays.

An empty heap is represented by an empty array [].

2fill in blank

medium

Complete the code to get the index of the left child of a node at index i.

DSA Typescript

function leftChild(i: number): number {
  return [1];
}

Drag options to blanks, or click blank then click option'

A2 * i

B2 * i + 1

Ci + 1

D2 * i - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 2 * i which is the index of the right child.

Using i + 1 which is just the next element.

In a heap stored as an array, left child index = 2 * i + 1.

3fill in blank

hard

Fix the error in the code to get the parent index of a node at index i.

DSA Typescript

function parent(i: number): number {
  return Math.floor([1]);
}

Drag options to blanks, or click blank then click option'

A(i - 1) / 2

Bi / 2

C(i + 1) / 2

Di - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using i / 2 which is incorrect for zero-based arrays.

Using i - 1 which is just the previous element.

Parent index = floor((i - 1) / 2) in a heap array.

4fill in blank

hard

Fill both blanks to check if a node at index i has a left child within heap size.

DSA Typescript

function hasLeftChild(i: number, size: number): boolean {
  return [1] < [2];
}

Drag options to blanks, or click blank then click option'

A2 * i + 1

B2 * i

Csize

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using 2 * i instead of 2 * i + 1 for left child.

Comparing with i instead of size.

Left child index is 2 * i + 1 and must be less than heap size.

5fill in blank

hard

Fill all three blanks to swap elements at indices i and j in the heap array.

DSA Typescript

function swap(heap: number[], i: number, j: number): void {
  const temp = heap[[1]];
  heap[[2]] = heap[[3]];
  heap[[3]] = temp;
}

Drag options to blanks, or click blank then click option'

Ai

Bj

Dtemp

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing indices i and j in assignments.

Using temp as an index instead of a value.

Swap uses temp to hold heap[i], then assigns heap[j] to heap[i], and temp back to heap[j].

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