数据结构与算法之最大优先队列

数据结构与算法之最大优先队列

        普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在某些情况下，我们可能需要找出 队列中的最大值或者最小值，例如使用一个队列保存计算机的任务，一般情况下计算机的任务都是有优先级的，我 们需要在这些计算机的任务中找出优先级最高的任务先执行，执行完毕后就需要把这个任务从队列中移除。普通的 队列要完成这样的功能，需要每次遍历队列中的所有元素，比较并找出最大值，效率不是很高，这个时候，我们就 可以使用一种特殊的队列来完成这种需求，优先队列。

最大优先队列

堆的结构可以让我们很方便的找到并删除最大值，我们就可以基于堆来实现最大优先队列。

最大优先队列的API设计：

 最大优先队列的代码实现

public class MaxPriorityQueue> {
    //存储堆中元素
    private final T[] items;
    //记录元素个数
    private int number;

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

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

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

    //判断堆中i索引处元素是否小于j索引处元素
    public boolean less(int i,int j){
        return items[i].compareTo(items[j])<0;
    }
    //交换i索引和j索引处的元素
    public void exchange(int i,int j){
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    //往堆中插入一个元素
    public void insert(T t){
        items[++number] = t;
        //上浮调整
        floatUp(number);
    }

    //删除堆中最大的元素,并返回这个最大元素
    public T delMax(){
        //堆中第一个元素即为最大的元素
        T max = items[1];
        //交换索引1处和最大索引处的元素，让完全二叉树最后一个元素变为临时根结点
        //items[1] = items[number]; //此方式也可行
        exchange(1,number);
        //删除掉最大索引处的值
        items[number] = null;
        number--;
        //使用下沉算法，让临时根结点处于合适的位置
        sink(1);
        return max;
    }


    //对堆中k索引处元素做上浮调整,使索引k处元素处于合适的位置
    private void floatUp(int k) {
        while (k>1){
            //比较k索引处元素与其父结点处元素大小，如果k大于其父结点处元素，则交换位置
            if (less(k/2,k)){
                exchange(k/2,k);
            }
            //变换k
            k = k/2;
        }
    }

    //使用下沉算法，使索引k处元素在堆中处于一个正确的位置
    private void sink(int k){
        //循环判断索引k处元素与其左右子结点处元素大小
        while (2*k <= number){
            //记录左右子结点中较大者元素的索引
            int max;
            if (2*k+1 <= number){
                if (less(2*k,2*k+1)){
                    max = 2*k+1;
                }else {
                    max = 2*k;
                }
            }else {
                max = 2*k;
            }
            //如果索引k处元素大于max处索引的元素,则说明索引k处元素处于正确的位置，结束循环，停止下沉
            if (!less(k,max)){
                break;
            }
            //交换索引k和索引max处的元素
            exchange(k,max);
            //变化k的值
            k = max;
        }
    }


    public static void main(String[] args) {
        String[] arr = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
        MaxPriorityQueue queue = new MaxPriorityQueue<>(20);
        for (String str : arr){
            queue.insert(str);
        }
        System.out.println(queue.size());

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

    }


}

测试结果

 以上是自己敲的demo，如有不正确的地方，还请谅解，希望跟CSDN的伙伴们共勉，每天记录一点点，每天进步一点点