Heap Sort is a comparison-based sorting technique based on a Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for the remaining elements.

Think of a King of the Hill contest:

1. You have a big group of people.
2. You organize them into a "Heap" where the strongest person is always at the top (The Root).
3. The King (Max element) leaves the hill and goes into the "Finished" line.
4. The remaining people reorganize themselves until a new King is at the top.
5. The new King leaves and joins the line.
6. When the hill is empty, your "Finished" line is perfectly sorted from strongest to weakest.

---

Complexity Analysis

• Time: $O(n \log n)$ in all cases.
• Space: $O(1)$. This is its superpower! Unlike Merge Sort, it needs zero extra memory. Unlike Quick Sort, it doesn't even need recursion stack space if implemented iteratively.

Key Characteristics

• In-Place: Yes.
• Stable: No.
• Comparison-Based: Yes.

---

javascript Standard
/**
 * Main Heap Sort Function
 */
function heapSort(arr) {
  const n = arr.length;

  // 1. Build Max Heap (Rearrange array)
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // 2. Extract elements from heap one by one
  for (let i = n - 1; i > 0; i--) {
    // Move current root to end
    [arr[0], arr[i]] = [arr[i], arr[0]];

    // Call max heapify on the reduced heap
    heapify(arr, i, 0);
  }
  
  return arr;
}

/**
 * Helper: Max Heapify a subtree rooted with node i
 */
function heapify(arr, n, i) {
  let largest = i;
  let left = 2 * i + 1;
  let right = 2 * i + 2;

  // If left child is larger than root
  if (left < n && arr[left] > arr[largest]) largest = left;

  // If right child is larger than largest so far
  if (right < n && arr[right] > arr[largest]) largest = right;

  // If largest is not root
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];

    // Recursively heapify the affected sub-tree
    heapify(arr, n, largest);
  }
}

---

When to use Heap Sort?

If you are strictly memory-constrained and cannot afford $O(n)$ space (Merge Sort) or the $O(n^2)$ worst-case risk (Quick Sort), Heap Sort is your best friend.

Common Questions

• Compare Merge Sort, Quick Sort, and Heap Sort.
• How do you build a heap in $O(n)$ time? (Answer: Start from the last non-leaf node and heapify down).
• What is the difference between a Max-Heap and a Min-Heap?
• Can you use a Heap to find the Top K elements in an array? (Answer: Yes, in $O(n \log k)$ time).