堆排序的应用-优先队列

堆排序在排序复杂性的研究中有着重要的地位，因为它是我们所知的唯一能够同时最优的利用空间和时间的方法-在最坏的情况下它能保证使用～2NlgN次比较和恒定的额外空间。

在开始了解优先队列之前我们先了解一下堆的特性：

一个大根堆有这么个特性，它的爸爸总是比它的俩孩子的值大;除了这个最基本的以外，你还要知道第k个元素的左孩子是2k，右孩子是2k+1;知道这个以后，下面我们需要实现两个方法，高效的删除最大元素和插入元素。

如果新插入一个数，那么根据前面的特性，只需要不断循环的用自身和自己的爸爸（k/2）比较大小，根据比较结果判断是否要交换位置即可;如果要删掉一个最大的数，只需要将根与最后一个数交换位置(因为根是大根堆中最大的数)，将其脱离堆结构，然后将根节点不断和它的孩子（2K、2K+1）比较大小，下沉到合适位置即可；

为了满足k,2k,2k+1的这种层级关系，后续将舍弃数组下标为0的位置，因为2*0会影响到这种层级关系的判断。

下面我们说一下下沉（sink）和上浮（swim）的实现方法

上浮

如果堆的有序状态因为某个节点比它的父节点更大而被打破，那么我们就需要通过交换它和它的父节点来修复堆。

private void swim(int k){

    while(k > 1 && less(k/2,k)){
        exch(k/2,k);
        k = k/2;
    }

}

下沉

与上浮相反，如果堆有序被打破，k节点想要下沉到合适的位置，代码应该这么写。

private void sink(int k){

    while(2*k <= N){
        int j = 2*k;
        if(j < N && less(j,j+1)) j++;
        if(!less(k,j)) break;
        exch(k,j);
        k = j;
    }
}

基于堆的优先队列

下面我们实现一下堆的优先队列。优先队列由一个基于堆的完全二叉树表示，存储于数组pq[1…N]中,pq[0]不用，代码如下：

public class MaxPQ<Key extends Comparable<Key>>{

    private Key[] pq;
    private int N = 0;

    public MaxPQ(int maxN){
        pq = (Key[]) new Comparable[maxN + 1];
    }

    public boolean isEmpty(){
        return N == 0;
    }

    public int size (){

        return N;

    }

    public void insert(Key v){

        pq[++N] = v;
        swim(N);

    }

    public Key delMax(){
        Key max = pq[1];
        exch(1,N--);
        pq[N+1] = null;
        sink(1);
        return max;
    }

    private boolean less(int i,int j){
        return pq[i] < pq[j];
    }

    private void exch(i,j){

        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;

    }

    private void swim(int k){
        ...
    }

    private void sink(int k){
        ...
    }

}

在insert()中，将N加1并把新元素添加到数组最后，然后用swim()恢复秩序。在delMax()中。从pq[1]中得到需要返回的元素，然后将pq[N]移动到pq[1],将N减一并用sink()恢复对的秩序。将pq[N+1]设为null，以便GC回收其所占空间。