堆排序和基于堆的扩展

堆排序

首先描述和实现堆排序，以排序结果为从小到大为例：

1. 堆的基本性质是：子结点的键值或索引总是小于（或者大于）它的父节点。
2. 首先要将要排序的数组构建成一个堆，即让它满足堆的性质：从第一个非叶子节点起到根节点进行调整，让子节点不大于父节点
3. 将根节点和最后一个叶子节点交换
4. 从根节点开始往下一级一级调整使重新满足堆的性质
5. 再转到3，直到所有结点都交换过了

详细的图解可以参考这里

public class HeapSort {
    private int[] arr;
    public HeapSort(int[] arr){
        this.arr = arr;
    }

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

    /**
     * 调整索引为 index 处的数据，使其符合堆的特性。
     *
     * @param index 需要堆化处理的数据的索引
     * @param len 未排序的堆（数组）的长度
     */
    private void maxHeapify(int index, int len){
        int li = (index << 1) + 1;
        int ri = li + 1;
        int cMax = li;

        if(li > len) return;
        if(ri <= len && arr[ri] > arr[li]){
            cMax = ri;
        }
        if(arr[cMax] > arr[index]){
            swap(cMax, index);
            maxHeapify(cMax, len);
        }
    }

    public void sort(){
        /*
         *  第一步：将数组堆化
         *  beginIndex = 第一个非叶子节点。
         *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
         *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
         */
        int len = arr.length - 1;
        int beginIndex = (len - 1) >> 1;
        for(int i = beginIndex; i >= 0; i--){
            maxHeapify(i, len);
        }

        /*
         * 第二步：对堆化数据排序
         * 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
         * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。
         * 直至未排序的堆长度为 0。
         */
        for(int i = len; i > 0; i--){
            swap(0, i);
            maxHeapify(0, i - 1);
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6};
        new HeapSort(arr).sort();
        System.out.println(Arrays.toString(arr));
    }
}

数据流中的中位数

基于堆可以做很多的扩展，以找数据流中的中位数为例：

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有值排序之后位于中间的数值。如果数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

需要注意的是，数据流是不断读入的，可能需要动态的输出中位数。

基于堆的解法：
用一个大顶堆和一个小顶堆，维持大顶堆的数都小于等于小顶堆的数，且两者的个数相等或差1。中位数就在两个堆顶的数之中。
java中若想使用堆可以用PriorityQueue，内部是用小顶堆实现的

class MedianFinder {

    private Queue<Long> small = new PriorityQueue(),    //左半部分，源数据从大到小排序，实现方法是数据前面加一个负号
                        large = new PriorityQueue();  //右半部分，数据源从小到大排序（默认）

    public void addNum(int num) {
        large.add((long) num);   //先加到右半部分
        small.add(-large.poll());  //再加大左半部分
        if (large.size() < small.size())  //发现右半部分小了
            large.add(-small.poll());  //再移回来
    }

    public double findMedian() {
        return large.size() > small.size()
               ? large.peek()
               : (large.peek() - small.peek()) / 2.0;
    }
};