Nothing special here. It’s just a blog post for summarising my algorithm learning course. Probably this was taught in the University but I don’t remember anything, I have no idea about its definition and applications until I take this course. Part 1 here Binary Heap & Heapsort Summary - Part 1 - Binary Heap

The Idea

Heapsort has two phases: build a max-heap from the array, then repeatedly remove the maximum to fill the array from the back. We use the array S O R T E X A M P L E (N = 11) as the example.

• Start with array of keys in arbitrary order

• Create a max-heap with all N keys

• Repeatedly remove the maximum key (in place) to create a sorted array

First step: Heap construction

Build heap using bottom-up method. Start with the lowest nodes and go up each level, use sink operation to correct the heap. Highlighted arrows show the path each sunk node travels.

Starting point (arbitrary order):

All the nodes in the lowest level (M, P, L, E at indices 8-11) are already 1-node binary heaps, so we start sinking from index N/2 = 5 and work back to the root.

sink(5) on E - it is smaller than child L, so it sinks down to index 10:

sink(4) on T - nothing to do, T is already larger than both children:

sink(3) on R - smaller than child X, so it sinks to index 6:

sink(2) on O - it sinks through T down to index 9:

sink(1) on S - smaller than child X, so it sinks to index 3, giving the final max-heap:

We finally transform an arbitrary array into a heap-ordered array.

for (int k = N/2; k >= 1; k--)
 sink(a, k, N);

Second step: Sortdown

In order to transform a heap-ordered array into a sorted array, we will repeatedly remove the largest item in the heap, one at a time. Refer to part 1 for the idea on how to remove the maximum item in a heap. The only difference is that after exchanging the max with the last item, we will keep it in the array instead of completely removing it out.

Starting point (a heap-ordered array):

Remove the largest item, one at a time, and park it at the end of the array. The first iteration swaps the max X with the last leaf, shrinks the heap (so X becomes the first sorted item), then sinks the new root E back down into place:

Repeating this until the heap is empty leaves the array fully sorted:

while (N > 1) {
 swap(a, 1, N--);
 sink(a, 1, N);
}

Java Implementation

public class Heap {
    public static void sort(Comparable[] a) {
        int N = a.length;
        // build the heap
        for (int k = N/2; k >= 1; k--)
            sink(a, k, N);

        // convert heap to sorted array
        while (N > 1)
        {
            exch(a, 1, N);
            sink(a, 1, --N);
        }
    }

    private static void sink(Comparable[] a, int k, int N) {
        // implemented in part 1
    }

    private static boolean less(Comparable[] a, int i, int j) { /* compare */ }

    private static void swap(Comparable[] a, int i, int j) { /* swap */ }
}

Heapsort Characteristics

• Heapsort is an In-place sorting algorithm with N logN worst-case
• Compare to the other sorting algorithm
  • Mergesort: not in-place, linear extra space required.
  • Quicksort: in-place, but quadratic time in worst case.
• Heapsort is optimal for both time and space, but:
  • Inner loop longer than Quicksort’s
  • Makes poor use of cache memory