Heap Sort

Heap Sort is a comparison-based sorting algorithm that builds a binary heap and sorts the elements efficiently. It works by repeatedly removing the largest element from the heap and adding it to the sorted part of the array. Heap Sort is known for its excellent time complexity and stability.

How Heap Sort Works

1. Heapify the Array:

   • Build a binary heap from the unsorted array, rearranging the elements.

2. Sorting:

   • While the heap is not empty:
     • Remove the largest element from the heap and add it to the sorted part of the array.
     • Re-heapify the remaining elements.

3. Completion:

   • When the heap is empty, the array is fully sorted.

Key Features

• Efficient: Heap Sort has an efficient average and worst-case time complexity.

• In-Place Sorting: It sorts the array in place without requiring additional memory.

• Stable: It maintains the relative order of equal elements.

Efficiency

• Time Complexity: The time complexity of Heap Sort is O(n log n), making it efficient for large datasets.

• Space Complexity: Heap Sort has a space complexity of O(1) as it sorts elements in place.

Advantages

• Efficient for large datasets.
• Stable and suitable for a variety of data types.

Disadvantages

• May not be as intuitive to implement as some other sorting algorithms.

Heap Sort Implementation in JavaScript

Here's an example of Heap Sort implemented in JavaScript:

function heapSort(arr) {
    function heapify(arr, n, i) {
        let largest = i;
        const left = 2 * i + 1;
        const 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);
        }
    }
 
    const 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);
    }
}
 
const unsortedArray = [12, 34, 54, 2, 3];
heapSort(unsortedArray);
console.log("Sorted Array:", unsortedArray);