Implementing Heap Sort

1. The Two Phases of Heap Sort

Heap sort works in two distinct phases, both performed on the same array in-place:

1. Heapify Phase: Transform the entire unsorted input array into a max-heap. We will use the efficient $O(N)$ buildHeap algorithm we learned in the previous lesson. After this phase, the largest element in the array is guaranteed to be at the root (index 0).

2. Sort-down Phase: Repeatedly extract the largest element from the heap and move it to its final sorted position at the end of the array.

   • Swap the root element (the current maximum) with the last element of the heap.
   • The largest element is now at the end of the array, in its correct sorted position.
   • Decrease the considered size of the heap by one, effectively "locking in" the sorted element at the end.
   • The new root element may violate the max-heap property. Restore the heap by calling heapify (or siftDown) on the root of the now smaller heap.
   • Repeat this process until the heap is empty.

Let's watch a video that visualizes this entire process.

The key insight is that by swapping the max element with the last element of the heap, we are simultaneously moving the largest unsorted item to its final place while also using that now-vacant spot to continue the heap operations. This is what makes the algorithm in-place.

2. A Detailed Walkthrough

Let's dive deeper into the mechanics of the "sort-down" phase. The Happy Coders article provides an excellent set of diagrams that walk through this process step-by-step.

As you can see from the walkthrough, the process systematically places the largest elements at the end of the array, one by one, shrinking the heap from the right and growing the sorted portion from the right.

3. Java Implementation

Now, let's translate this logic into Java code. Given your background, you'll appreciate how the algorithm's logic maps directly to a clean implementation. The main heapSort method orchestrates the two phases, relying on a helper heapify function (the siftDown you know well) to maintain the heap property.

We will again refer to the Happy Coders article, as it provides a complete and well-structured Java implementation.

Let's break down the essential pieces of code you just reviewed.

The heapSort method:
This is the main driver. It first calls buildHeap and then enters the sorting loop.

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

    // Phase 1: Build a max-heap from the array.
    // We start from the last non-leaf node and go up to the root.
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Phase 2: One by one extract an element from heap
    for (int i = n - 1; i > 0; i--) {
        // Move current root (max element) to the end
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // call heapify on the reduced heap of size 'i'
        heapify(arr, i, 0);
    }
}

The heapify (sift-down) method:
This is the workhorse function that maintains the max-heap property.

// To heapify a subtree rooted with node i which is an index in arr[]. 
// n is the size of the heap.
void heapify(int[] arr, int n, 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 < 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) {
        // Swap arr[i] and arr[largest]
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;

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

Note: This version is recursive for clarity. The iterative version from the article is equally valid and slightly more optimized for space.

4. Algorithm Analysis and Properties

For technical interviews, simply knowing how to implement an algorithm is not enough. You must also understand its performance characteristics and trade-offs.

Time Complexity

• Heapify Phase (buildHeap): As we learned, this takes $O(N)$ time.
• Sort-down Phase: This loop runs $N-1$ times. In each iteration, we do one swap ($O(1)$) and one call to heapify on the root. The heapify operation's complexity is proportional to the height of the heap, which is $O(\log k)$ where $k$ is the current heap size. Since $k$ goes from $N-1$ down to 1, the total time for this phase is $O(N\log N)$.
• Total Time Complexity: $O(N)+O(N\log N)=O(N\log N)$. This is the time complexity for the worst, average, and best cases.

Space Complexity

Heap sort is an in-place algorithm. The sorting is done directly within the input array. If using an iterative heapify, you only need a few extra variables for loops and swaps, making the auxiliary space complexity $O(1)$. If using a recursive heapify, the space complexity becomes $O(\log N)$ due to the recursion call stack. For interviews, it's best to highlight the $O(1)$ potential with an iterative implementation.

Stability

Heap sort is not stable. This means that if there are two equal elements in the input array, their relative order is not guaranteed to be preserved in the sorted output. Long-range swaps during the heapify process can easily change their original order.

This quick video and detailed article section will help you consolidate these facts.

Conclusion

Congratulations! You've successfully implemented and analyzed Heap Sort. This is a significant milestone in your study of sorting algorithms. Its combination of $O(N\log N)$ time and $O(1)$ space complexity makes it a unique and powerful tool.

Key Takeaways:

• Heap Sort is an in-place sorting algorithm with a time complexity of $O(N\log N)$.
• It works in two phases: first building a max-heap ($O(N)$) and then repeatedly swapping the root with the last element and heapifying the reduced heap ($O(N\log N)$).
• Its auxiliary space complexity is $O(1)$ (for an iterative implementation), which is its main advantage over Merge Sort.
• Unlike Merge Sort, Heap Sort is not stable.

Preview of the Next Lesson:
The heap data structure isn't just for sorting. Its primary application is often as the backing structure for a Priority Queue. In our next lesson, we will implement a priority queue using the heap operations you now know so well and use it to solve common interview problems like finding the "Top K" elements in a stream of data.