Heap sort 🍇

What's Heap Sort? 💡

Heap Sort is an efficient, comparison-based sorting algorithm that is particularly well-suited for situations where you need to sort a large amount of data. It operates by transforming the input array into a binary heap (a special tree-based data structure) and repeatedly extracting the maximum (for ascending order) or minimum (for descending order) element from the heap and placing it at the end of the sorted portion of the array. Heap Sort was first developed by J.W.J. Williams in 1964 and later refined by Robert W. Floyd in 1965.

Time Complexity: ⏱️

It guarantees this time complexity regardless of the input data's initial order.

Space Complexity: ⚙️

Heap Sort typically has a space complexity of O(1) since it sorts the array in-place without requiring additional memory for temporary data structures. However, if you create a separate heap data structure, it would consume additional memory.

Strengths and Weaknesses of Heap Sort 🤓

Strengths: ⚪️

• Efficient: O(n log n) time complexity.
• In-Place Sorting: Doesn't require extra memory.
• Input-Order Insensitive.

Weaknesses: 🔴

• Not Stable.
• Complex Implementation.

Here's a simple implementation of Heap Sort in JavaScript:

Code 🖋

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);
  }
}
 
function heapSort(arr) {
  const n = arr.length;
 
  // Build max heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
 
  // Extract elements from the heap one by one
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]]; // Swap the root (maximum) element with the last element
    heapify(arr, i, 0); // Call heapify on the reduced heap
  }
 
  return arr;
}
 
// Example usage:
const unsortedArray = [10, 4, 8, 5, 12, 2, 6, 11, 3, 9, 7, 1];
const sortedArray = heapSort(unsortedArray);
console.log(sortedArray); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

Conclusion 🗯️

Heap Sort is an efficient sorting algorithm with a consistent worst-case and average-case time complexity of O(n*log(n)). It excels at sorting large datasets and operates in-place, which makes it memory-efficient. However, it is not a stable sorting algorithm, and its implementation can be more complex compared to some other sorting methods. Heap Sort is an excellent choice when you need a reliable and efficient sorting solution for a wide range of input data.