Heap Sort

Pro: In-place sorting algorithm with O(NlogN) worst-case

1. Heap construction uses <= 2N compares and exchanges
2. Heapsort uses <= 2NlgN compares and exchanges

Con:

1. Inner loop longer than quick sort
2. Make poor use of cache memory
3. Not stable

Heap Sort 模板

1. Create max-heap with all N keys (bottom-up)
2. Repeatedly remove the maximum key

Heap construction: 只需要把所有拥有子节点的Node Sink一遍，也就是说从N/2 开始向上遍历一遍

public class Heap {
    public static void sort(Comparable[] temp) {
        int len = temp.length;
        for (int i = len / 2; i >= 0; i--) {
            sink(temp, i, len);
        }
        while (len >= 0) {
            swap(temp, 0, len);
            sink(temp, 0, --len);
        }
    }
    private static void sink(Comparable[] temp, int k, int len) {
        while (2 * k < len) {
            int child = k * 2;
            if (child + 1 < len && less(temp, child, child + 1)) child++;
            if (!less(temp, k, child)) break;
            swap(temp, k, child)
            k = child;
        }
    }
    private static void less(Comparable[] temp, int i, int j) {
        return temp[i].compareTo(temp[j]) < 0;
    }
    private static boolean swap(Comparable[] temp, int i, int j) {
        Comparable m = temp[i];
        temp[i] = temp[j];
        temp[j] = m;
    }
}

Problems:

Taxicab numbers. A taxicab number is an integer that can be expressed as the sum of two cubes of integers in two different ways: a3+b3=c3+d3. For example, 1729=93+103=13+123. Design an algorithm to find all taxicab numbers with a, b, c, and d less than n.

Version 1: Use time proportional to n2logn and space proportional to n2.
Version 2: Use time proportional to n2logn and space proportional to n.

Hints:

Version 1: Form the sums a^3+b^3 and sort.
Version 2: Use a min-oriented priority queue with n items.