Practice Heap Sort Implementation

In this practice area, you can implement your own version of the Heap Sort algorithm. Complete the code below by filling in the TODOs and test your implementation.

Key Steps to Implement

1. Build a max heap from the input array
2. Extract elements one by one from the heap
3. Implement the heapify operation to maintain the heap property

Your Code

Test Cases

Your implementation will be tested against the following arrays:

Input: [5, 1, 4, 2, 8]

Expected: [1, 2, 4, 5, 8]

Input: [38, 27, 43, 3, 9, 82, 10]

Expected: [3, 9, 10, 27, 38, 43, 82]

Hints

• Remember that the heap building phase starts from the first non-leaf node (n/2-1) and works backwards.
• In the extraction phase, swap the maximum element (root) with the last element of the heap.
• After each extraction, the heap size decreases by one.
• The heapify function needs to recursively maintain the max heap property.

Solution Template

1function heapSort(arr) {
2  const n = arr.length;
3  
4  // Build max heap
5  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
6    heapify(arr, n, i);
7  }
8  
9  // Extract elements one by one
10  for (let i = n - 1; i > 0; i--) {
11    // Swap root with last element
12    [arr[0], arr[i]] = [arr[i], arr[0]];
13    
14    // Heapify the reduced heap
15    heapify(arr, i, 0);
16  }
17  
18  return arr;
19}
20
21function heapify(arr, n, i) {
22  let largest = i;
23  const left = 2 * i + 1;
24  const right = 2 * i + 2;
25  
26  // Check if left child exists and is greater than root
27  if (left < n && arr[left] > arr[largest]) {
28    largest = left;
29  }
30  
31  // Check if right child exists and is greater than largest so far
32  if (right < n && arr[right] > arr[largest]) {
33    largest = right;
34  }
35  
36  // If largest is not root, swap and continue heapifying
37  if (largest !== i) {
38    [arr[i], arr[largest]] = [arr[largest], arr[i]];
39    heapify(arr, n, largest);
40  }
41}