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

阳光穿透心脏的1/2处 2023-10-03 17:55 30阅读 0赞

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

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YUJveV9YWkw_size_18_color_FFFFFF_t_70_g_se_x_16][]

### 最大优先队列 ###

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

最大优先队列的API设计：

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YUJveV9YWkw_size_20_color_FFFFFF_t_70_g_se_x_16][]

最大优先队列的代码实现

/**
     * @author: xuzhilei6656
     * @create: 2021-12-10 17:47
     * @description: 最大优先队列
     **/
    public class MaxPriorityQueue<T extends Comparable<T>> {
        //存储堆中元素
        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<String> 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);
            }
    
        }
    
    
    }

测试结果

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YUJveV9YWkw_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

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

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YUJveV9YWkw_size_18_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/dc642e5f1fef4b368fe8f8939acaa600.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmF2YUJveV9YWkw=,size_18,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YUJveV9YWkw_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/7f0af381e7f54ae9a7a84c07937bcb41.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmF2YUJveV9YWkw=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBASmF2YUJveV9YWkw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/c0b89fa24ed94e0081d22bde68038127.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASmF2YUJveV9YWkw=,size_20,color_FFFFFF,t_70,g_se,x_16