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    // Move current root to end
12    [arr[0], arr[i]] = [arr[i], arr[0]];
13    
14    // Call max heapify on the reduced heap
15    heapify(arr, i, 0);
16  }
17  
18  return arr;
19}
20
21// To heapify a subtree rooted with node i which is
22// an index in arr[]. n is size of heap
23function heapify(arr, n, i) {
24  let largest = i; // Initialize largest as root
25  const left = 2 * i + 1;
26  const right = 2 * i + 2;
27  
28  // If left child is larger than root
29  if (left < n && arr[left] > arr[largest]) {
30    largest = left;
31  }
32  
33  // If right child is larger than largest so far
34  if (right < n && arr[right] > arr[largest]) {
35    largest = right;
36  }
37  
38  // If largest is not root
39  if (largest !== i) {
40    [arr[i], arr[largest]] = [arr[largest], arr[i]];
41    
42    // Recursively heapify the affected sub-tree
43    heapify(arr, n, largest);
44  }
45}
46
47// Example usage
48const array = [12, 11, 13, 5, 6, 7];
49console.log('Original array:', array);
50heapSort(array);
51console.log('Sorted array:', array);

1. Heap Data Structure

A binary heap is represented as an array, where for a node at index i:

• Parent node is at index ⌊(i-1)/2⌋
• Left child is at index 2*i + 1
• Right child is at index 2*i + 2

2. Heapify Operation

The heapify function is used to maintain the heap property by ensuring that for any node i, its children are smaller (in a max heap) than itself. If a child is larger, it swaps positions with the parent and recursively applies heapify to the affected subtree.

3. Build Heap Phase

Starting from the first non-leaf node (at index n/2-1, where n is the array length) and working backwards to the root, the heapify function is applied to each node. This efficiently transforms the array into a max heap.

4. Sort Phase

Once the heap is built:

1. Swap the root (maximum element) with the last element in the heap
2. Exclude the last element from further heapify operations by reducing the heap size
3. Heapify the root element to restore the max heap property
4. Repeat until all elements are processed