Heap Concept Structure and Properties in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to get the index of the left child in a heap array.

DSA Javascript

function leftChildIndex(parentIndex) {
  return 2 * parentIndex [1] 1;
}

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

A+

B/

C*

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction instead of addition.

Using multiplication instead of addition.

Using division which is incorrect here.

The left child index in a heap array is calculated as 2 * parentIndex + 1.

2fill in blank

medium

Complete the code to get the index of the parent node in a heap array.

DSA Javascript

function parentIndex(childIndex) {
  return Math.floor((childIndex [1] 1) / 2);
}

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

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Adding 1 instead of subtracting 1.

Not using floor which causes wrong index.

Using multiplication or division incorrectly.

The parent index is calculated as floor((childIndex - 1) / 2) in a heap array.

3fill in blank

hard

Fix the error in the code to check if a node has a right child in the heap array.

DSA Javascript

function hasRightChild(index, heapSize) {
  return (2 * index + [1]) < heapSize;
}

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

A-1

B0

C1

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 instead of 2 for right child index.

Using 0 or negative numbers which are invalid here.

The right child index is 2 * index + 2, so we check if this is less than heapSize.

4fill in blank

hard

Fill both blanks to create a function that swaps two elements in a heap array.

DSA Javascript

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

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

A[i]

B[j]

C.i

D.j

Attempts:

3 left

💡 Hint

Common Mistakes

Using dot notation instead of bracket notation.

Mixing indices between temp and heap assignments.

To swap elements, use bracket notation with indices: heap[i] and heap[j].

5fill in blank

hard

Fill all three blanks to complete the siftDown function that maintains the heap property.

DSA Javascript

function siftDown(heap, index, heapSize) {
  let largest = index;
  const left = 2 * index + [1];
  const right = 2 * index + [2];

  if (left < heapSize && heap[left] > heap[[3]]) {
    largest = left;
  }

  if (right < heapSize && heap[right] > heap[largest]) {
    largest = right;
  }

  if (largest !== index) {
    swap(heap, index, largest);
    siftDown(heap, largest, heapSize);
  }
}

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

A1

B2

Cindex

Dlargest

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up left and right child offsets.

Comparing with largest instead of index in first if condition.

Left child index is 2*index+1, right child is 2*index+2, and compare heap[left] with heap[index].

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 child nodes

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

C. All leaf nodes are greater than the root node

D. The tree is always a complete binary tree but unordered

Solution

1. Step 1: Understand max heap property

   A max heap requires that each parent node is greater than or equal to its children.

2. Step 2: Compare options with max heap definition

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

3. Final Answer:

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

4. Quick Check:

   Max heap = parent ≥ children [OK]

Hint: Max heap means parent is always bigger or equal [OK]

Common Mistakes:

• Confusing max heap with min heap property
• Thinking leaf nodes must be bigger than root
• Ignoring the complete binary tree requirement

2. Which of the following is the correct way to represent a heap in JavaScript using an array?

easy

A. Parent at index i, left child at i + 1, right child at i + 2

B. Parent at index i, left child at 2*i + 1, right child at 2*i + 2

C. Parent at index i, left child at 2*i, right child at 2*i + 1

D. Parent at index i, left child at i - 1, right child at i - 2

Solution

1. Step 1: Recall array indexing for heap

   In zero-based arrays, left child index = 2*i + 1, right child index = 2*i + 2.

2. Step 2: Match options with formula

   Parent at index i, left child at 2*i + 1, right child at 2*i + 2 matches the correct formula for zero-based indexing heaps.

3. Final Answer:

   Parent at index i, left child at 2*i + 1, right child at 2*i + 2 -> Option B

4. Quick Check:

   Heap array indexing = 2*i+1, 2*i+2 [OK]

Hint: Remember zero-based indexing: left=2i+1, right=2i+2 [OK]

Common Mistakes:

• Using one-based indexing formulas incorrectly
• Swapping left and right child indices
• Using i+1 or i+2 which is wrong for heap

3. Consider the following JavaScript code that builds a max heap from an array:

const arr = [3, 9, 2, 1, 4, 5];
function maxHeapify(arr, i, n) {
  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]];
    maxHeapify(arr, largest, n);
  }
}

function buildMaxHeap(arr) {
  let n = arr.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    maxHeapify(arr, i, n);
  }
}

buildMaxHeap(arr);
console.log(arr);

What is the output printed?

medium

A. [3, 9, 2, 1, 4, 5]

B. [9, 3, 5, 1, 4, 2]

C. [5, 4, 3, 1, 9, 2]

D. [9, 4, 5, 1, 3, 2]

Solution

1. Step 1: Understand buildMaxHeap process

   Start heapifying from last non-leaf node at index 2 (value 2), then index 1 (value 9), then index 0 (value 3).

2. Step 2: Trace heapify calls

   Initial: [3,9,2,1,4,5]
   Heapify i=2: left=5 (5>2), largest=5, swap 2-5: [3,9,5,1,4,2]. Heapify 5: no children.
   Heapify i=1: left=3(1<9), right=4(4<9), no swap.
   Heapify i=0: left=1(9>3), largest=1; right=2(5<9), swap 0-1: [9,3,5,1,4,2]. Heapify 1 (val=3): left=3(1<3), right=4(4>3), largest=4, swap 1-4: [9,4,5,1,3,2]. Heapify 4: no children.

3. Final Answer:

   [9, 4, 5, 1, 3, 2] -> Option D

4. Quick Check:

   Max heap array after build = [9,4,5,1,3,2] [OK]

Hint: Heapify from bottom non-leaf nodes up [OK]

Common Mistakes:

• Not heapifying recursively after swap
• Confusing indices for children
• Assuming original array order remains

4. The following JavaScript function is intended to insert a new value into a max heap represented as an array. Identify the bug:

function insertHeap(arr, value) {
  arr.push(value);
  let i = arr.length - 1;
  while (i > 0) {
    let parent = Math.floor(i / 2);
    if (arr[parent] < arr[i]) {
      [arr[parent], arr[i]] = [arr[i], arr[parent]];
      i = parent;
    } else {
      break;
    }
  }
}

medium

A. Parent index calculation should be Math.floor((i - 1) / 2)

B. The loop should run while i >= 0

C. The swap should happen only if arr[parent] > arr[i]

D. The function should remove the last element before inserting

Solution

1. Step 1: Check parent index formula in zero-based heap

   In zero-based arrays, parent index = Math.floor((i - 1) / 2), not Math.floor(i / 2).

2. Step 2: Understand impact of wrong parent index

   Using Math.floor(i / 2) causes incorrect parent calculation, breaking heap property restoration.

3. Final Answer:

   Parent index calculation should be Math.floor((i - 1) / 2) -> Option A

4. Quick Check:

   Parent index = (i-1)//2 in zero-based heap [OK]

Hint: Parent index in zero-based heap = (i-1)//2 [OK]

Common Mistakes:

• Using i/2 instead of (i-1)/2 for parent
• Loop condition allowing i=0 to cause errors
• Swapping when parent is larger, not smaller

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

hard

A. [2, 5, 8, 10, 15, 20, 1] -> [2, 5, 8, 10, 15, 20, 1] -> [1, 5, 8, 10, 15, 20, 2]

B. [2, 5, 8, 10, 15, 20, 1] -> [1, 5, 8, 10, 15, 20, 2]

C. [2, 5, 8, 10, 15, 20, 1] -> [2, 5, 1, 10, 15, 20, 8] -> [1, 5, 2, 10, 15, 20, 8]

D. [2, 5, 8, 10, 15, 20, 1] -> [1, 2, 5, 10, 15, 20, 8]

Solution

1. Step 1: Insert value at end

   Insert 1 at the end: [2, 5, 8, 10, 15, 20, 1]

2. Step 2: Heapify up swaps

   Compare 1 with parent at index 2 (value 8), swap: [2, 5, 1, 10, 15, 20, 8]
   Compare 1 with new parent at index 0 (value 2), swap: [1, 5, 2, 10, 15, 20, 8]

3. Step 3: Final heap state

   Heap property restored with 1 at root.

4. Final Answer:

   [2, 5, 8, 10, 15, 20, 1] -> [2, 5, 1, 10, 15, 20, 8] -> [1, 5, 2, 10, 15, 20, 8] -> Option C

5. Quick Check:

   Heapify up swaps child with parent until order restored [OK]

Hint: Heapify up swaps child with parent until order restored [OK]

Common Mistakes:

• Not swapping with correct parent index
• Stopping heapify too early
• Incorrect final heap array after swaps