算法读书笔记-排序算法-优先队列

优先队列是一种抽象数据类型，它表示了一组值和对这些值的操作，它可以让我们每次从中取出权重最大的值.

优先队列的实现

初级实现

数组实现（有序）
在insert的时候对数组排按照权值好序，push只要拿掉最后一个数.
数组实现（无需）
在push时取出全职最大（或最小）的值，insert直接拿最后一个数

二叉堆实现

用数组表示二叉数(若n为根节点则2n和2n+1为它的两个子节点),插入时将它放到最后一个位置，然后上浮（swim）。取出时将它的根节点取出然后把最后一个一个值放到根节点下沉（sink）

上浮的实现

    /*
     * 从k开始，由下至上的堆有序化
     */
    public void swim(int k){
        while(k<1&&less(k/2,k)){
            exch(k,k/2);
            k = k/2;
        }
    }

下沉的实现

    /*
     * 从k开始自上而下的堆有序化
     */
    public void sink(int k,int N){
        while(2*k<=N){
            int j = 2*k;
            if(j<N&&less(j,j+1)) j++;//找出左右子树中较大的值
            if(!less(k, j)) break;//如果它的子树最大值比它大就退出循环
            exch(j, k);
            k=j;
        }
    }

基于堆实现的优先队列

public class MaxPQ<Key extends Comparable<Key>>{
    private Key[] pq;
    private int N = 0;
    
    public void 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;
    }
    
    /*
     * 从k开始，由下至上的堆有序化
     */
    public void swim(int k){
        while(k<1&&less(k/2,k)){
            exch(k,k/2);
            k = k/2;
        }
    }
    /*
     * 从k开始自上而下的堆有序化
     */
    public 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(j, k);
            k=j;
        }
    }
    
    public static void exch(int i,int j){int temp = i;i = j; j = temp;}//需要改写
    public static boolean less(int v,int w){return v<w? true:false;}//需要改写
}

堆排序

主要思想：利用堆的上浮和下沉可以有序化堆实现数组有序的摆放

public static void sort(Comparable[] a){
        int N = a.length;
        for(int k = N/2;k>=1;k--)//将大数沉到最下面
            sink(a,k,N);
        while(N>1){
            exch(a,1,N--);//将最上面的数和最下面的数交换
            sink(a,1,N);//将最上面的数下沉，重构数组
        }
    }