It’s time to summon the power of the Heap Sort algorithm — the unsung hero of sorting, the algorithm equivalent of a construction crane that picks up the biggest item and drops it right where it belongs 💪🏗️

This is one of those O(n log n) sorting beasts that:

• Sorts in-place ✅

• Uses no recursion ✅

• Has worst-case O(n log n) time ✅

• And secretly underpins Java's PriorityQueue and other cool stuff ✅

Let’s dive right in.

---

🔼 Heap Sort: The Priority-Based Sorting Powerhouse

“Why scan the whole array for the biggest number when I can just build a structure where the biggest number is always at the top?”
— Heap Sort, casually smarter than brute force

---

🧠 What is Heap Sort?

Heap Sort uses a binary heap to sort an array.
Specifically:

1. Build a max heap (largest value at the top/root)

2. Swap the max element (root) with the last element in the array

3. Reduce the heap size, then heapify again

4. Repeat until the array is sorted

---

🔢 Time & Space Complexity

---

🏗️ What’s a Heap Again?

A heap is a complete binary tree with two properties:

• Complete: All levels are full except possibly the last

• Heap order:

  • Max-Heap → each parent ≥ its children

  • Min-Heap → each parent ≤ its children

Heap is usually implemented as an array.
For index i:

• Left child = 2i + 1

• Right child = 2i + 2

• Parent = (i - 1) / 2

---

🛠️ Java Array Implementation of Heap Sort

Let’s write it from scratch. No PriorityQueue. No shortcuts.

java
CopyEdit
public class HeapSort {

    public void sort(int[] arr) {
        int n = arr.length;

        // Step 1: Build max heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // Step 2: Extract elements from heap one by one
        for (int i = n - 1; i > 0; i--) {
            // Move current root to end
            swap(arr, 0, i);

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

    // To heapify subtree rooted at index i
    private void heapify(int[] arr, int heapSize, int i) {
        int largest = i;         // Initialize largest as root
        int left = 2 * i + 1;    // Left child
        int right = 2 * i + 2;   // Right child

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

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

        // If largest is not root
        if (largest != i) {
            swap(arr, i, largest);
            // Recursively heapify the affected subtree
            heapify(arr, heapSize, largest);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // Demo
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};

        HeapSort sorter = new HeapSort();
        sorter.sort(arr);

        System.out.println("Sorted array:");
        for (int value : arr) {
            System.out.print(value + " ");
        }
    }
}

---

🧪 How It Works

Let’s walk through a quick example:

css
CopyEdit
Input: [4, 10, 3, 5, 1]

1. Build max heap:
   → [10, 5, 3, 4, 1]

2. Move largest (10) to end:
   → [1, 5, 3, 4, 10]

3. Heapify the remaining:
   → [5, 4, 3, 1, 10]

Repeat until it’s sorted: → [1, 3, 4, 5, 10] ✅

---

🔍 Why Heap Sort Rocks

• ✅ Consistent O(n log n) time

• ✅ In-place sorting

• ✅ Doesn’t rely on recursion

• ✅ Excellent for memory-limited environments

• ✅ Good fallback when stability isn’t required

---

⚠️ Caveats

• ❌ Not stable (equal elements can get swapped out of order)

• ❌ Can be slower in practice than Quick Sort (because of frequent swaps & less cache-friendly)

---

🧠 TL;DR (Too Long, Didn’t Heapify)

• Heap Sort = build max heap → extract max repeatedly

• Array-based implementation

• Time complexity: O(n log n) for all cases

• Space: O(1), no extra arrays needed

• Not stable, but solid and consistent

• Excellent for teaching heap logic and priority-based sorting

---

🎓 Final Thoughts From the Sorting Arena

Merge Sort is clean.
Quick Sort is fast.
Heap Sort? It’s a brick wall.
Unshakeable. Efficient. Reliable.
You might not always use it, but when you do — it gets the job done without asking for anything extra.