优先队列

优先队列
普通队列是一种先进先出的数据结构，元素在队尾追加，在队列头删除。然而在某些情况下，我们需要找到最大值，最小值，或某些特定元素进行删除，这个时候我们就可以用优先队列来实现这种需求。
1.1 最大优先队列
可以获取并删除队中最大的值。
实现方式和上篇讲的堆大同小异，因此不再细讲。

public class MaxPriorityQueue<T extends Comparable<T>> {
    private T[] items;
    private int N;
    public MaxPriorityQueue(int capacity){
        this.items=(T [])new Comparable[capacity+1];
        this.N=0;
    }
    //获取队列中元素的个数
    public int size(){
        return N;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return N==0;
    }
    //判断i处的元素是否小于j处的元素
    public boolean less(int i,int j){
        return items[i].compareTo(items[j])<0;
    }
    //交换i索引处的值和j索引处的值
    public void exch(int i,int j){
        T temp=items[i];
        items[i]=items[j];
        items[j]=temp;
    }
    //向堆中插入一个元素
    public void insert(T t){
        items[++N]=t;
        swim(N);
    }
    //使用上浮算法，使索引k处的元素能处在正确的位置
    public void swim(int k){
        //通过循环不断比较当前节点的值和父结点的值，如果父节点的值比当前结点小，则交换位置
        while (k>1){
            //比较当前结点和父结点
            if (less(k/2,k)){
                exch(k,k/2);
            }
            k=k/2;
        }
    }
    //删除堆中最大的元素，并返回其值
    public T delMax(){
        T max = items[1];
        //交换索引1处的元素和最大索引处的元素，让最右侧的元素成为根结点
        exch(1,N);
        //删除最大索引处的元素
        items[N]=null;
        //元素个数-1
        N--;
        //通过下沉调整堆，让堆重新有序
        sink(1);
        return max;
    }
    //使用下沉算法，使索引k处的元素能处在正确的位置
    public void sink(int k){
        //通过循环不断比较当前结点和左子节点和右子结点元素大小，如果当前元素小，则交换元素位置
        while (2*k<=N){
            //获取当前结点的子结点中的较大结点
            int bigger; //记录较大元素的索引
            if (2*k+1<=N){
                if (less(2*k,2*k+1)){
                    bigger=2*k+1;
                }
                else{
                    bigger=2*k;
                }
            }else{
                bigger=2*k;
            }
            //比较当前结点和较大结点
            if (!less(k,bigger)){
                break;
            }
            //交换k索引处的值和bigger索引处的值
            exch(k,bigger);
            //变换k的值
            k=bigger;
        }
    }
}

1.2最小优先队列
最小优先队列的实现思想和最大优先队列大同小异。不同点有2.
①最小元素放在数组的索引1处
②每个结点的数据总是小于等于它的两个子结点的数据
代码也只是下沉算法和上浮算法有略微不同。
上浮算法

 public void swim(int k){
        //通过循环不断比较当前节点的值和父结点的值，如果父节点的值比当前结点小，则交换位置
        while (k>1){
            //比较当前结点和父结点
            if (less(k,k/2)){
                exch(k,k/2);
            }
            k=k/2;
       }
    }

下沉算法

public void sink(int k){
        //通过循环不断比较当前结点和左子节点和右子结点元素大小，如果当前元素大，则交换元素位置
        while (2*k<=N){
            //获取当前结点的子结点中的较小结点
            int smaller; //记录较大元素的索引
            if (2*k+1<=N){
                if (less(2*k,2*k+1)){
                    smaller=2*k;
                }
                else{
                    smaller=2*k+1;
                }
            }else{
                smaller=2*k;
            }
            //比较当前结点和较小结点
            if (less(k,smaller)){
                break;
            }
            //交换k索引处的值和bigger索引处的值
            exch(k,smaller);
            //变换k的值
            k=smaller;
        }
    }

完整代码

//最小优先队列
public class MinPriorityQueue<T extends Comparable<T>> {
    private T[] items;
    private int N;
    public MinPriorityQueue(int capacity){
        this.items=(T [])new Comparable[capacity+1];
        this.N=0;
    }
    //获取队列中元素的个数
    public int size(){
        return N;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return N==0;
    }
    //判断i处的元素是否小于j处的元素
    public boolean less(int i,int j){
        return items[i].compareTo(items[j])<0;
    }
    //交换i索引处的值和j索引处的值
    public void exch(int i,int j){
        T temp=items[i];
        items[i]=items[j];
        items[j]=temp;
    }
    //向堆中插入一个元素
    public void insert(T t){
        items[++N]=t;
        swim(N);
    }
    //使用上浮算法，使索引k处的元素能处在正确的位置
    public void swim(int k){
        //通过循环不断比较当前节点的值和父结点的值，如果父节点的值比当前结点小，则交换位置
        while (k>1){
            //比较当前结点和父结点
            if (less(k,k/2)){
                exch(k,k/2);
            }
            k=k/2;
        }
    }
    //删除堆中最小的元素，并返回其值
    public T delMin(){
        T min= items[1];
        //交换索引1处的元素和最大索引处的元素，让最右侧的元素成为根结点
        exch(1,N);
        //删除最大索引处的元素
        items[N]=null;
        //元素个数-1
        N--;
        //通过下沉调整堆，让堆重新有序
        sink(1);
        return min;
    }
    //使用下沉算法，使索引k处的元素能处在正确的位置
    public void sink(int k){
        //通过循环不断比较当前结点和左子节点和右子结点元素大小，如果当前元素大，则交换元素位置
        while (2*k<=N){
            //获取当前结点的子结点中的较小结点
            int smaller; //记录较大元素的索引
            if (2*k+1<=N){
                if (less(2*k,2*k+1)){
                    smaller=2*k;
                }
                else{
                    smaller=2*k+1;
                }
            }else{
                smaller=2*k;
            }
            //比较当前结点和较小结点
            if (less(k,smaller)){
                break;
            }
            //交换k索引处的值和bigger索引处的值
            exch(k,smaller);
            //变换k的值
            k=smaller;
        }
    }
}

1.3 索引优先队列
首先，我们用items数组来存储元素，并将这些元素和唯一的索引关联。然后再创建一个pq数组，用来存储items数组的索引。但如果我们想找到某一元素，只能对pq数组进行遍历，如果存储的元素很多，则查找元素的效率就会很低。因此，我们创建一个qp数组，存储pq数组的逆序。即qp数组存储的元素是pq数组的索引，qp数组的索引是pq数组的元素。因此，qp数组的索引就是items数组的索引。查找元素时，先看qp，再看pq。如图所示：

构造方法

//存储堆中的元素
    private T[] items;
    //保存每个元素在items中的索引，pq数组要求堆有序
    private int[] pq;
    //pq的逆序，即pq的索引作为值，值作为索引
    private int[] qp;
    private int N;
    public IndexMinPriorityQueue(int capacity){
        this.items=(T [])new Comparable[capacity+1];
        this.pq=new int[capacity+1];
        this.qp=new int[capacity+1];
        this.N=0;
        //默认情况下，队列中没有存储任何元素，qp中的元素为-1
        for (int i = 0; i < qp.length; i++) {
            qp[i]=-1;
        }
    }

判断堆i处的元素是否小于j处的元素

public boolean less(int i,int j){
        return items[pq[i]].compareTo(items[pq[j]])<0;
    }

交换i索引处的值和j索引处的值

public void exch(int i,int j){
        //交换pq中的数据
        int tem=pq[i];
        pq[i]=pq[j];
        pq[j]=tem;
        //更新qp中的数据
        qp[pq[i]]=i;
        qp[pq[j]]=j;
    }

向队列中插入一个元素，并关联索引

public void insert(int i,T t){
        //判断i是否被关联，如果被关联，则不让插入
        if (contains(i)){
            return;
        }
        //元素个数+1
        N++;
        //把数据存储到items对应的i位置处
        items[i]=t;
        //把i存储到pq中
        pq[N]=i;
        //通过qp来记录pq中的i
        qp[i]=N;
        //通过堆上浮来调整堆
        swim(N);
    }

删除队列中最小的元素，并返回队列关联的索引

public int delMin(){
        //获取最小元素关联的索引
        int minIndex=pq[1];
        //交换pq索引1处和最大索引处的元素
        exch(1,N);
        //删除qp中对应的内容
        qp[pq[N]]=-1;
        //删除pq最大索引处的内容
        pq[N]=-1;
        //删除items对应的内容
        items[minIndex]=null;
        //元素个数-1
        N--;
        //下沉调整
        sink(1);
        return minIndex;
    }

删除索引i关联的元素

 public void delete(int i){
         //找到i在pq中的索引
        int k = qp[i];
        //交换索引k处的值和N处的值
        exch(k,N);
        //删除qp中的内容
        qp[pq[N]]=-1;
        //删除pq中的内容
        pq[N]=-1;
        //删除items中的内容
        items[k]=null;
        //元素个数-1
        N--;
        //堆的调整
        swim(k);
        sink(k);
    }

把与索引i关联的元素改为t

public void changeItem(int i,T t){
        //修改items数组中i位置的元素为t
        items[i]=t;
        //找到i在pq中的位置，
        int k = qp[i];
        // 调整堆
        swim(k);
        sink(k);
    }

下沉算法

private void sink(int k) {
        //通过循环不断比较当前结点和左子节点和右子结点元素大小，如果当前元素大，则交换元素位置
        while (2*k<=N){
            //获取当前结点的子结点中的较小结点
            int smaller; //记录较大元素的索引
            if (2*k+1<=N){
                if (less(2*k,2*k+1)){
                    smaller=2*k;
                }
                else{
                    smaller=2*k+1;
                }
            }else{
                smaller=2*k;
            }
            //比较当前结点和较小结点
            if (less(k,smaller)){
                break;
            }
            //交换k索引处的值和bigger索引处的值
            exch(k,smaller);
            //变换k的值
            k=smaller;
        }
    }

上浮算法

 private void swim(int k) {
        //通过循环不断比较当前节点的值和父结点的值，如果父节点的值比当前结点小，则交换位置
        while (k>1){
            //比较当前结点和父结点
            if (less(k,k/2)){
                exch(k,k/2);
            }
            k=k/2;
        }
    }

完整代码

//索引优先队列
public class IndexMinPriorityQueue<T extends Comparable<T>> {
    //存储堆中的元素
    private T[] items;
    //保存每个元素在items中的索引，pq数组要求堆有序
    private int[] pq;
    //pq的逆序，即pq的索引作为值，值作为索引
    private int[] qp;
    private int N;
    public IndexMinPriorityQueue(int capacity){
        this.items=(T [])new Comparable[capacity+1];
        this.pq=new int[capacity+1];
        this.qp=new int[capacity+1];
        this.N=0;
        //默认情况下，队列中没有存储任何元素，qp中的元素为-1
        for (int i = 0; i < qp.length; i++) {
            qp[i]=-1;
        }
    }
    //获取队列中元素的个数
    public int size(){
        return N;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return N==0;
    }
    //判断堆i处的元素是否小于j处的元素
    public boolean less(int i,int j){
        return items[pq[i]].compareTo(items[pq[j]])<0;
    }
    //交换i索引处的值和j索引处的值
    public void exch(int i,int j){
        //交换pq中的数据
        int tem=pq[i];
        pq[i]=pq[j];
        pq[j]=tem;
        //更新qp中的数据
        qp[pq[i]]=i;
        qp[pq[j]]=j;
    }
    //判断k对应的元素是否存在
    public boolean contains(int k){
        return qp[k]!=-1;
    }
    //最小元素关联的索引
    public int minIndex(){
        return pq[1];
    }
    //向队列中插入一个元素，并关联索引
    public void insert(int i,T t){
        //判断i是否被关联，如果被关联，则不让插入
        if (contains(i)){
            return;
        }
        //元素个数+1
        N++;
        //把数据存储到items对应的i位置处
        items[i]=t;
        //把i存储到pq中
        pq[N]=i;
        //通过qp来记录pq中的i
        qp[i]=N;
        //通过堆上浮来调整堆
        swim(N);
    }
    //删除队列中最小的元素，并返回队列关联的索引
    public int delMin(){
        //获取最小元素关联的索引
        int minIndex=pq[1];
        //交换pq索引1处和最大索引处的元素
        exch(1,N);
        //删除qp中对应的内容
        qp[pq[N]]=-1;
        //删除pq最大索引处的内容
        pq[N]=-1;
        //删除items对应的内容
        items[minIndex]=null;
        //元素个数-1
        N--;
        //下沉调整
        sink(1);
        return minIndex;
    }
    //删除索引i关联的元素
    public void delete(int i){
         //找到i在pq中的索引
        int k = qp[i];
        //交换索引k处的值和N处的值
        exch(k,N);
        //删除qp中的内容
        qp[pq[N]]=-1;
        //删除pq中的内容
        pq[N]=-1;
        //删除items中的内容
        items[k]=null;
        //元素个数-1
        N--;
        //堆的调整
        swim(k);
        sink(k);
    }

    //把与索引i关联的元素改为t
    public void changeItem(int i,T t){
        //修改items数组中i位置的元素为t
        items[i]=t;
        //找到i在pq中的位置，
        int k = qp[i];
        // 调整堆
        swim(k);
        sink(k);
    }
    //下沉算法
    private void sink(int k) {
        //通过循环不断比较当前结点和左子节点和右子结点元素大小，如果当前元素大，则交换元素位置
        while (2*k<=N){
            //获取当前结点的子结点中的较小结点
            int smaller; //记录较大元素的索引
            if (2*k+1<=N){
                if (less(2*k,2*k+1)){
                    smaller=2*k;
                }
                else{
                    smaller=2*k+1;
                }
            }else{
                smaller=2*k;
            }
            //比较当前结点和较小结点
            if (less(k,smaller)){
                break;
            }
            //交换k索引处的值和bigger索引处的值
            exch(k,smaller);
            //变换k的值
            k=smaller;
        }

    }
    //上浮算法
    private void swim(int k) {
        //通过循环不断比较当前节点的值和父结点的值，如果父节点的值比当前结点小，则交换位置
        while (k>1){
            //比较当前结点和父结点
            if (less(k,k/2)){
                exch(k,k/2);
            }
            k=k/2;
        }
    }
}

b站详细讲解网址：http://yun.itheima.com/course/639.html