[数据结构与算法]数据结构与算法（java）：优先队列

优先队列

普通队列：先进先出，后进后出
优先队列：与入队和出队顺序无关，只与规定的优先级有关。
优先队列的队首元素是优先级最高的元素
优先队列可以用不同的底层数据结构来实现，只是各实现方式的时间复杂度不同而已，通常用堆实现

下面优先队列的实现均使用堆的数据结构

优先队列按照其作用的不同分为下面两种
最大优先队列：可以获取并删除队列中最大的值
最小优先队列，可以获取并删除队列中最小的值

相关知识
数据结构与算法（java）：线性表-堆
数据结构与算法（java）：线性表-队列

最大优先队列

特点：
最大的元素放在数组的索引1处，每个结点的数据总是大于等于它的两个子结点的数据。（因为用到的底层数据结构是堆，所以处理起来很像在处理堆）

代码如下

public class MaxPriorityQueue <T extends Comparable<T>>{
    //存储堆中元素
    private T[] items;
    //记录对中元素的个数
    private int Num;

    //构造器
    public MaxPriorityQueue(int capacity) {
        this.items = (T []) new Comparable[capacity+1];
        this.Num = 0;
    }

    //获取队列中元素的个数
    public int size(){
        return Num;
    }

    //判断队列是否为空
    public boolean isEmpty(){
        return Num == 0;
    }

    //判断堆中索引i处的元素是否小于索引j处的元素
    private boolean less(int i, int j){
        return items[i].compareTo(items[j])<0;
    }

    //交换堆中索引和j索引处的值
    private void exchange(int i, int j){
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    //往堆中插入一个元素
    public void insert(T t){
        items[++Num] = t;
        swim(Num);
    }

    //删除堆中最大的元素，并返回最大元素
    public T delMax(){
        T max = items[1];
        exchange(1,Num);
        Num--;
        sink(1);
        return max;
    }

    //使用上浮算法，让大的值往上移动
    private void swim(int k){
        while(k>1){
            if(less(k/2,k)){
                exchange(k/2,k);
            }
            k = k/2;
        }
    }

    //使用下沉算法，让k位置的值往下沉
    private void sink(int k){
        //当存在左子结点时
        while(2*k<=Num){
            int max;
            //当右子结点存在时
            if(2*k+1<=Num){
                //比较左右子结点的大小，得到一个较大值
                if(less(2*k,2*k+1)){
                    max = 2*k+1;
                }else{
                    max = 2*k;
                }
            }else{
                max = 2*k;
            }

            if(!less(k,max)){
                break;
            }

            exchange(k,max);

            k = max;
        }
    }
}

测试类

public static void main(String[] args) {
        MaxPriorityQueue<String> queue = new MaxPriorityQueue(10);
        queue.insert("A");
        queue.insert("B");
        queue.insert("C");
        queue.insert("D");
        queue.insert("E");
        queue.insert("F");
        queue.insert("G");


        while(!queue.isEmpty()){
            String max = queue.delMax();
            System.out.println(max + " ");
        }

    }

结果：

G
F
E
D
C
B
A

最小优先队列

与最大优先队列相反，它将最小的元素放在数组的索引1处，每个结点的数据总是小于等于它的两个子结点的数据。实现过程差不多。。。

代码如下

public class MinPriorityQueue<T extends Comparable<T>> {
    private T[] items; //存储在堆中的元素
    private int Num; //堆中元素个数

    public MinPriorityQueue(int capacity){
        this.items = (T[]) new Comparable[capacity + 1];
        this.Num = 0;
    }

    //获取队列中元素的个数
    public int size(){
        return -1;
    }

    //判断队列是否为空
    public boolean isEmpty(){
        return Num == 0;
    }

    //判断索引i和索引j处的值的大小
    private boolean less(int i, int j){
        return items[i].compareTo(items[j])<0;
    }

    private void exchange(int i, int j){
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }
    //往堆中插入一个元素
    public void insert(T t){
        items[++Num] = t;
        swim(Num);
    }

    public T  delMin(){
        T min = items[1];
        exchange(1,Num);
        Num--;
        sink(1);
        return min;
    }

    //上浮算法，将插入的元素放到堆中合适的位置上（这里是将小的值往上移动）
    private void swim(int k){
        while(k > 1){
            //通过循环比较当前结点和其父结点的大小，如果当前结点小于父结点，则交换位置
            if(less(k,k/2)){
                exchange(k,k/2);
            }
            k = k/2;
        }
    }

    //下沉算法，主要作用是将要删除的元素移动到堆中合适的位置,这里是将最小的元素移动到数组最大索引处,并且为和1位置处交换的值找到合适的位置
    private void sink(int k){
        while(2*k<=Num){
            int min;
            if(2*k+1<=Num){
            //找到子结点中较小值
                if(less(2*k,2*k+1)){
                    min = 2*k;
                }else{
                    min = 2*k+1;
                }
            }else{
                min = 2*k;
            }

            if(less(k,min)){
                break;
            }

            exchange(k,min);

            k = min;
        }
    }
}

测试类

public static void main(String[] args) {
        MinPriorityQueue<String> queue = new MinPriorityQueue(10);
        queue.insert("E");
        queue.insert("F");
        queue.insert("D");
        queue.insert("G");
        queue.insert("A");
        queue.insert("B");
        queue.insert("C");

        while(!queue.isEmpty()){
            String min = queue.delMin();
            System.out.print(min + " ");
        }
    }

结果

A B C D E F G

索引优先队列

仔细的了解了上述的最大优先和最小优先队列的时候可以发现，这两个队列都可以快速的访问到队列中的最大元素和最小元素，但是他们都有一个缺点，那就是无法通过索引访问已经存在于优先队列中的队列，并且更新他们，为了实现这个目的，再优先队列的基础上实现了索引优先队列。。。

下面以索引优先队列来举例。。。

原理和思路

1、要想通过某个数来获取指定的数据元素，那么就必须把这两绑定在一起，让他们相互关联，我们可以通过数组来实现，通过数组的索引来获取对应的值。因此，设置一个数组T[] items来存储数据元素，在往队列中完成插入时，绑定好数据和其索引。

2、完成上一步后，虽然给每个元素关联了一个整数，并且可以使用这个整数快速获取到该元素，但是items数组中元素都是随机的，并没有按照从小到大或者从大到小的顺序排列好，为了排好序，增加一个数组int[] pq来保存每个元素在items数组中的索引，通过让pq数组变有序，使得在拿到items数组中的元素时也是有序的，举例来说就是pq[1]对应的数据元素items[pq[1]]要小于等于pq[2]和pq[3]对应的数据元素items[pq[2]]和items[pq[3]]。

pq数组中存放的数据是items数组排序后的对应数据的索引。如果堆要调整，那么就可直接调整pq数组，通过pq数组可以找到item数组中的数据。但此时还有个弊端，当items数组中某个值修改了之后，需要找到pq数组中对应items数组中修改值的索引并进行修改，当数据较少的时候可以选择通过遍历来找到pq中存放items的索引的那个值，但当数据很大的时候，遍历的效率就会很低。

3、为了较快速的找到pq中存放的items数组的索引，有增加了一个数组qp，这个数组用来存放pq的逆序，就是说，
pq[6] = 1, qp[1] = 6；

当有了pq数组后，如果要修改items[0] = “H”,那么就可以先通过索引0，在qp数组中找到qp的索引：qp[0] = 9;之后可以直接调整pq[9]即可。

具体代码实现如下

public class indexMinPriorityQueue<T extends Comparable<T>> {
    //存储堆中的元素
    private T[] items;
    //存储每个元素在items数组中的索引，pq数组需要堆有序
    private int[] pq;
    //存储qp的逆序，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处的元素
    private boolean less(int i, int j){
        return items[pq[i]].compareTo(items[pq[j]])<0;
    }

//-----------------------------------------------------------------------
    //交换堆中元素的值
    private void exchange(int i, int j){
        //交换pq数组中的数据
        int temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;

        //更新qp数组中的值
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }

//-----------------------------------------------------------------------
    //判断k对应的元素是否存在
    public boolean contains(int k){
        //qp数组中默认值为-1
        return qp[k] != -1;
    }

//-----------------------------------------------------------------------
    //最小元素关联的索引
    public int minIndex(){
        return pq[1];
    }

//-----------------------------------------------------------------------
    //在队列中插入一个元素，并关联索引i
    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处和最大索引处的元素
        exchange(1,N);

        //删除qp中对应内容
        qp[pq[N]] = -1;

        //删除pq中对应的内容
        pq[N] = -1;

        //删除items中对应的内容
        items[minIndex] = null;

        //元素个数减1
        N--;

        //下沉调整
        sink(1);

        return N;
    }

//-----------------------------------------------------------------------
    //删除索引i关联的元素
    public void delete(int i){
        //找到i在pq中的索引
        int k = qp[i];

        //交换pq中索引空出的值和索引N处的值
        exchange(k,N);

        //删除qp中的内容
        qp[pq[N]] = -1;

        //删除pq中的内容
        pq[N] = -1;

        //删除items中的内容
        items[k] = null;

        //元素数量-1
        N--;
        //堆的调整
        sink(k);
        swim(k);
    }

//-----------------------------------------------------------------------
    //修改i位置处的元素为t
    public void revise(int i, T t){
        //修改items数组中i位置的元素为t
        items[i] = t;

        //找到i在pq中出现的位置
        int k = qp[i];
        //堆调整
        sink(k);
        swim(k);
    }

//-----------------------------------------------------------------------
    //上浮算法
    private void swim(int k){
        while(k>1){
            if(less(k,k/2)){
                exchange(k,k/2);
            }
            k = k/2;
        }
    }

//-----------------------------------------------------------------------
    //下沉算法
    private void sink(int k){
        while(2*k<=N){
            int min;
            if(2*k+1<=N){
                if(less(2*k, 2*k+1)){
                    min = 2*k;
                }else{
                    min = 2*k+1;
                }
            }else{
                min = 2*k;
            }

            if(less(k,min)){
                break;
            }

            exchange(k,min);
            k = min;
        }
    }
}

测试代码

public static void main(String[] args) {
        indexMinPriorityQueue<String> queue = new indexMinPriorityQueue<>(10);
        queue.insert(0,"A");
        queue.insert(1,"C");
        queue.insert(2,"F");

        //测试修改
        queue.revise(2,"8");

        //测试删除
        while(!queue.isEmpty()){
            int index = queue.delMin();
            System.out.println(index + "");
        }
    }

结果：

2
1
0