Heap Sort Algorithm in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Heap Sort on a small array

What is the output of the following JavaScript code that uses heap sort to sort an 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] > arr[largest]) {
    largest = left;
  }

  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }

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

function heapSort(arr) {
  let n = arr.length;

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

  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }
}

let array = [4, 10, 3, 5, 1];
heapSort(array);
console.log(array.join(' -> ') + ' -> null');

A 1 -> 4 -> 3 -> 5 -> 10 -> null

B 10 -> 5 -> 4 -> 3 -> 1 -> null

C 1 -> 3 -> 4 -> 5 -> 10 -> null

D 5 -> 10 -> 4 -> 3 -> 1 -> null

💡 Hint

Heap sort sorts the array in ascending order by building a max heap first.

Heap sort first builds a max heap, then repeatedly swaps the root with the last element and heapifies the reduced heap. The final array is sorted ascending.

🧠 Conceptual

intermediate

Understanding heapify in heap sort

In the heap sort algorithm, what is the main purpose of the heapify function?

A To build a max heap by ensuring the subtree rooted at a given index satisfies the heap property

B To swap the first and last elements of the array

C To sort the array by comparing adjacent elements

D To reverse the array after sorting

💡 Hint

Heapify fixes the heap property starting from a node downwards.

Heapify ensures that the subtree rooted at a given index is a max heap by comparing the node with its children and swapping if needed.

🔧 Debug

advanced

Identify the error in this heap sort code snippet

What error will this JavaScript code produce when running heap sort?

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] < arr[largest]) {
    largest = left;
  }

  if (right < n && arr[right] < arr[largest]) {
    largest = right;
  }

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

function heapSort(arr) {
  let n = arr.length;

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

  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }
}

let array = [4, 10, 3, 5, 1];
heapSort(array);
console.log(array.join(' -> ') + ' -> null');

A The array will be sorted in descending order instead of ascending

B SyntaxError due to incorrect swap syntax

C The array will remain unsorted

D TypeError because heapify is called with wrong arguments

💡 Hint

Check the comparison operators in heapify function.

The heapify function uses '<' instead of '>' which builds a min heap, causing the array to be sorted descending.

❓ Predict Output

advanced

Heap sort output with duplicate elements

What is the output of the following heap sort code when sorting an array with duplicates?

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] > arr[largest]) {
    largest = left;
  }

  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }

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

function heapSort(arr) {
  let n = arr.length;

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

  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }
}

let array = [4, 10, 3, 10, 5, 1];
heapSort(array);
console.log(array.join(' -> ') + ' -> null');

A 10 -> 10 -> 5 -> 4 -> 3 -> 1 -> null

B 1 -> 3 -> 4 -> 5 -> 10 -> 10 -> null

C 1 -> 3 -> 4 -> 10 -> 5 -> 10 -> null

D 1 -> 4 -> 3 -> 5 -> 10 -> 10 -> null

💡 Hint

Heap sort handles duplicates by sorting them in ascending order.

Heap sort sorts the array ascending including duplicates, so duplicates appear next to each other in sorted order.

🚀 Application

expert

Heap sort time complexity analysis

What is the time complexity of heap sort in the worst case and why?

A O(n^2) because heapify is called n times and each call takes O(n)

B O(n) because the array is sorted in a single pass

C O(log n) because heapify is a logarithmic operation

D O(n log n) because building the heap takes O(n) and each of the n removals takes O(log n)

💡 Hint

Consider the cost of building the heap and the cost of extracting elements.

Building the heap is O(n), and each of the n removals requires O(log n) heapify calls, totaling O(n log n).