Heap

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements.

The basic idea is to build a max heap (for ascending order) or a min heap (for descending order) from the input data and repeatedly remove the maximum (or minimum) element from the heap and put it into the sorted array.

Here's how the heap sort algorithm works:

1. Build a max heap from the input array.

2. Swap the root element (maximum element) with the last element of the heap and decrease the size of the heap by 1.

3. Heapify the root element to maintain the heap property.

4. Repeat steps 2 and 3 until the size of the heap is 1.

pseudocode:

heapSort(arr):
    n = length(arr)
    
    // Build max heap
    for i from n/2 - 1 down to 0:
        heapify(arr, n, i)
    
    // Extract elements from heap one by one
    for i from n-1 down to 0:
        // Move current root to end
        swap(arr[0], arr[i])
        
        // Heapify the reduced heap
        heapify(arr, i, 0)

heapify(arr, n, i):
    largest = i
    left = 2*i + 1
    right = 2*i + 2
    
    // Check if left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left
        
    // Check if right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    // If largest is not root
    if largest != i:
        swap(arr[i], arr[largest])
        
        // Recursively heapify the affected sub-tree
        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);
    }

    return arr;
}

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);
    }
}

console.log(HeapSort(numbers));

In this implementation, heapify function is used to heapify a subtree rooted with node i, and heapSort function sorts the array using the heap data structure.

Finally, we use example usage to demonstrate how to sort an array using heap sort.