Why Heap Exists and What Sorted Array Cannot Do Efficiently in DSA Javascript - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a new element into a max heap.

DSA Javascript

function insert(heap, value) {
  heap.push(value);
  let index = heap.length - 1;
  while (index > 0) {
    let parent = Math.floor((index - 1) / [1]);
    if (heap[parent] >= heap[index]) break;
    [heap[parent], heap[index]] = [heap[index], heap[parent]];
    index = parent;
  }
}

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

A3

B2

C1

D4

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect divisor for parent calculation.

Not using Math.floor which causes wrong parent index.

In a binary heap, the parent index is calculated as Math.floor((index - 1) / 2). This helps maintain the heap property efficiently.

2fill in blank

medium

Complete the code to extract the maximum element from a max heap.

DSA Javascript

function extractMax(heap) {
  if (heap.length === 0) return null;
  const max = heap[0];
  heap[0] = heap.pop();
  let index = 0;
  while (true) {
    let left = 2 * index + 1;
    let right = 2 * index + 2;
    let largest = index;
    if (left < heap.length && heap[left] > heap[[1]]) largest = left;
    if (right < heap.length && heap[right] > heap[largest]) largest = right;
    if (largest === index) break;
    [heap[index], heap[largest]] = [heap[largest], heap[index]];
    index = largest;
  }
  return max;
}

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

Alargest

Bleft

Cright

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing left child with right child instead of current node.

Using wrong variable for comparison.

We compare the left child with the current node at index to find the largest value to maintain the max heap property.

3fill in blank

hard

Fix the error in the code that checks if a sorted array can efficiently insert a new element.

DSA Javascript

function insertSorted(arr, value) {
  let i = arr.length - 1;
  while (i >= 0 && arr[i] > [1]) {
    arr[i + 1] = arr[i];
    i--;
  }
  arr[i + 1] = value;
}

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

Avalue

Barr[i]

Ci

Darr[i + 1]

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing arr[i] with itself or wrong variable.

Using index variable instead of value.

We compare arr[i] with the new value to find the correct position to insert in the sorted array.

4fill in blank

hard

Fill both blanks to create a function that checks if a sorted array contains a value using binary search.

DSA Javascript

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) [1] 2);
    if (arr[mid] === target) return true;
    else if (arr[mid] [2] target) left = mid + 1;
    else right = mid - 1;
  }
  return false;
}

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

A+

B<

C/

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition or subtraction instead of division for mid calculation.

Incorrect comparison operators.

Mid index is calculated by dividing sum of left and right by 2. If arr[mid] is less than target, search right half by moving left to mid + 1; else search left half by moving right to mid - 1.

5fill in blank

hard

Fill all three blanks to create a function that builds a max heap from an unsorted array.

DSA Javascript

function heapify(arr, n, i) {
  let largest = i;
  let left = 2 * i + 1;
  let right = 2 * i + 2;

  if (left < n && arr[left] [1] arr[largest]) largest = left;
  if (right < n && arr[right] [2] arr[largest]) largest = right;

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, [3]);
  }
}

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

A>

B<

Ci

Dlargest

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' for max heap comparison.

Recursive call with wrong index.

To maintain max heap property, compare children with current largest. If a child is larger, update largest. Then recursively heapify the affected subtree starting at largest.