Heap Sort

function heapify(arr, n, i) {
    let largest = i;          // Initialize largest as root
    let left = 2 * i + 1;     // Left child index
    let right = 2 * i + 2;    // Right child index
    
    // If left child exists and is greater than root
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    
    // If right child exists and is greater than largest so far
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    
    // If largest is not root, swap and continue heapifying
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        
        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

function heapSort(arr) {
    const n = arr.length;
    
    // Phase 1: Build max heap
    // Start from last non-leaf node and heapify each node
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // Phase 2: Extract elements from heap one by one
    for (let i = n - 1; i > 0; i--) {
        // Move current root (maximum) to end
        [arr[0], arr[i]] = [arr[i], arr[0]];
        
        // Call heapify on the reduced heap
        heapify(arr, i, 0);
    }
    
    return arr;
}

// Array representation of heap:
// For element at index i:
// - Parent: Math.floor((i-1)/2)
// - Left child: 2*i + 1  
// - Right child: 2*i + 2

// Example:
const numbers = [4, 10, 3, 5, 1];
console.log("Original:", numbers);
heapSort(numbers);
console.log("Sorted:", numbers);