Heap Sort Explained: How It Works, Why It's Fast, and When to Use It

public class MaxHeapVisualizer {

    /**
     * Restores the max-heap property for a subtree rooted at 'rootIndex'.
     * 'heapSize' tells us how many elements are still part of the active heap
     * (elements beyond heapSize are already sorted and must not be touched).
     */
    static void heapify(int[] array, int heapSize, int rootIndex) {
        int largest = rootIndex;           // assume the root is the largest to start
        int leftChild = 2 * rootIndex + 1; // left child index in array
        int rightChild = 2 * rootIndex + 2; // right child index in array

        // Is the left child inside the heap AND larger than current largest?
        if (leftChild < heapSize && array[leftChild] > array[largest]) {
            largest = leftChild;
        }

        // Is the right child inside the heap AND larger than current largest?
        if (rightChild < heapSize && array[rightChild] > array[largest]) {
            largest = rightChild;
        }

        // If the largest element is NOT the root, we have a violation — fix it
        if (largest != rootIndex) {
            int temp = array[rootIndex];
            array[rootIndex] = array[largest];
            array[largest] = temp;

            // The swap may have broken the heap property further down — recurse
            heapify(array, heapSize, largest);
        }
    }

    public static void main(String[] args) {
        int[] scores = {3, 19, 7, 11, 5, 14};

        System.out.println("Before heapify on full array:");
        printArray(scores);

        // Build a max-heap from the bottom up.
        // We only need to heapify internal nodes (last internal node is at n/2 - 1).
        int n = scores.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(scores, n, i);
        }

        System.out.println("After building max-heap:");
        printArray(scores);  // index 0 will hold the largest value
    }

    static void printArray(int[] array) {
        System.out.print("[ ");
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println("]");
    }
}

public class HeapSort {

    /**
     * Restores max-heap property for the subtree rooted at rootIndex.
     * Only elements with index < heapSize are considered part of the heap.
     */
    static void heapify(int[] array, int heapSize, int rootIndex) {
        int largest = rootIndex;
        int leftChild = 2 * rootIndex + 1;
        int rightChild = 2 * rootIndex + 2;

        if (leftChild < heapSize && array[leftChild] > array[largest]) {
            largest = leftChild;
        }
        if (rightChild < heapSize && array[rightChild] > array[largest]) {
            largest = rightChild;
        }
        if (largest != rootIndex) {
            // Swap parent with the larger child to fix the violation
            int temp = array[rootIndex];
            array[rootIndex] = array[largest];
            array[largest] = temp;
            // The swapped child's subtree might now be violated — fix it too
            heapify(array, heapSize, largest);
        }
    }

    /**
     * Sorts the array in ascending order using heap sort.
     * Time:  O(n log n) in all cases
     * Space: O(log n) due to recursion stack (O(1) if heapify is iterative)
     */
    static void heapSort(int[] array) {
        int totalElements = array.length;

        // ── PHASE 1: Build a max-heap from the unsorted array ──
        // Start from the last internal node (index n/2 - 1) and work up to root.
        // Leaf nodes are trivially valid heaps, so we skip them.
        for (int i = totalElements / 2 - 1; i >= 0; i--) {
            heapify(array, totalElements, i);
        }

        // ── PHASE 2: Extract elements from the heap one by one ──
        for (int sortedBoundary = totalElements - 1; sortedBoundary > 0; sortedBoundary--) {
            // The root (index 0) is the current maximum — move it to its final position
            int temp = array[0];
            array[0] = array[sortedBoundary];  // root goes to the end of active heap
            array[sortedBoundary] = temp;       // last element takes the root spot

            // Heap just shrank by one. Restore max-heap property for the new root.
            heapify(array, sortedBoundary, 0);
        }
    }

    public static void main(String[] args) {
        // Real-world scenario: sorting student exam scores
        int[] examScores = {72, 45, 91, 38, 85, 60, 77, 55, 93, 42};

        System.out.println("Unsorted exam scores:");
        printArray(examScores);

        heapSort(examScores);

        System.out.println("Sorted exam scores (ascending):");
        printArray(examScores);

        // Edge cases — good habit to always verify these
        int[] singleElement = {99};
        heapSort(singleElement);
        System.out.println("Single element array: " + singleElement[0]);

        int[] alreadySorted = {1, 2, 3, 4, 5};
        heapSort(alreadySorted);
        System.out.print("Already sorted input: ");
        printArray(alreadySorted);

        int[] reverseOrder = {5, 4, 3, 2, 1};
        heapSort(reverseOrder);
        System.out.print("Reverse sorted input: ");
        printArray(reverseOrder);
    }

    static void printArray(int[] array) {
        System.out.print("[ ");
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println("]");
    }
}

import java.util.PriorityQueue;

/**
 * Real-world use case: finding the top-K highest exam scores
 * from a large dataset without sorting the entire array.
 *
 * Strategy: maintain a min-heap of size K.
 * If a new score beats the smallest score in the heap, it deserves a spot.
 * At the end, the heap contains exactly the K largest scores.
 *
 * Time:  O(n log K)  — far faster than O(n log n) when K is small
 * Space: O(K)        — only the heap, not the full dataset
 */
public class TopKScores {

    static int[] findTopKScores(int[] allScores, int k) {
        if (k <= 0 || k > allScores.length) {
            throw new IllegalArgumentException(
                "k must be between 1 and " + allScores.length
            );
        }

        // PriorityQueue in Java is a min-heap by default.
        // The smallest score in the heap sits at the front — easy to evict.
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);

        for (int score : allScores) {
            if (minHeap.size() < k) {
                // Heap isn't full yet — add unconditionally
                minHeap.offer(score);
            } else if (score > minHeap.peek()) {
                // New score beats the weakest score currently in top-K
                minHeap.poll();    // evict the smallest
                minHeap.offer(score); // admit the new contender
            }
            // Otherwise, score doesn't make the cut — skip it
        }

        // Drain the heap into an array (not yet sorted within top-K)
        int[] topK = new int[k];
        for (int i = 0; i < k; i++) {
            topK[i] = minHeap.poll();
        }
        return topK;
    }

    public static void main(String[] args) {
        int[] classScores = {
            67, 82, 91, 55, 78, 95, 60, 88, 73, 99,
            45, 84, 70, 93, 61, 77, 89, 52, 96, 64
        };

        int topCount = 5;
        int[] topStudents = findTopKScores(classScores, topCount);

        System.out.println("Top " + topCount + " exam scores from a class of " + classScores.length + ":");
        System.out.print("[ ");
        for (int score : topStudents) {
            System.out.print(score + " ");
        }
        System.out.println("]");
        System.out.println("(Order within top-K reflects heap eviction order, not rank)");
    }
}