数据结构——优先队列与堆

客官°小女子只卖身不卖艺 2022-05-13 19:21 409阅读 0赞

## 什么是优先队列？ ##

普通队列:先进先出，后进后出  
优先队列:出队顺序和入队顺序无关；和优先级相关，如医院中，病重先安排病床

### 优先队列的现实例子： ###

①cpu任务调度，动态选择优先级最高的任务执行  
②王者荣耀中，攻击键优先打敌人，无敌人时候优先打最近的小兵

### 关于优先队列的实现： ###

普通的线性结构和堆都可以作为优先队列的底层实现。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70][]

堆实现优先队列，在最坏的情况下，入队与出队的操作，时间复杂都为O(logn)

## 二叉堆 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 1][]

①堆是一棵完全二叉树

②堆中某个节点的值总是不大于其父节点的值，图示为最大堆

补充：在堆中，所有节点的值都大于他们的孩子节点，那么层次比较低的节点一定大于层次比较高的节点呢？

不一定，如16、13和19。

可以使用一个数组表示而不需要使用链，数组如图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 2][]

父子索引之间的关系
    parent(i) = i / 2;
    left  child(i) = 2 * i;
    right child(i) = 2 * i + 1;

索引也可以从0开始，但公式有所变化

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 3][]

父子索引之间的关系
    parent(i) = (i - 1 ) / 2;
    left  child(i) = 2 * i + 1;
    right child(i) = 2 * i + 2;

## 大根堆中 ##

### 向堆中添加一个元素(Sift Up上浮) ###

先添加，再上浮【满足父节点一定大于新添加的节点，否则(while)两者交换位置，并更新索引值】

/**
         * 向堆中添加元素
         */
        public void add(T t) {
            data.addLast(t);
            siftUp(data.getSize() - 1);
        }
        //上浮
        private void siftUp(int i) {
            while (i > 0 && data.get(i).compareTo(data.get(parent(i))) > 0) {
                //交换位置
                data.swap(i, parent(i));
                //更新i值
                i = parent(i);
            }
        }

### 堆中移除最大一个元素后(Sift Up下沉) ###

移除最大元素后，实际上变为了52和30为根节点的子树，为了简化操作，将索引值最大的元素size-1复制到索引0的位置，再删除size-1的元素，这样总的元素个数就保证了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 4][]

那么造成一个问题，16元素作为父节点并不大于它的两个子节点，所以需要有Sift Up下沉的动作，直到满足父节点元素值大于子节点元素值。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 5][]

每次我们需要下沉的元素都和子孩子比较，选择两个孩子中最大的元素，如果最大的元素比父节点更大的话，则子节点与父节点交换位置，此时父节点52就一定比左右节点都大了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 6][]

此时再将16与他的最大子节点进行比较，如果仍不满足父节点大于子节点的话，继续交换位置。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 7][]

此时再次比较16所处位置的子节点，满足父节点大于子节点，不需要交换位置，下沉操作结束Sift down。

/**
         * 查看堆中最大元素
         */
        public T findMax() {
            if (data.getSize() == 0)
                throw new IllegalArgumentException("堆中没有元素");
            return data.get(0);
        }
    
        /**
         * 取出堆中最大元素
         */
        public T extractMax() {
            T t = findMax();
            /**
             *  将堆中最大的元素删除
             *  1、将最后一个元素与第一个元素交换位置
             *  2、删除最后一个元素
             *  3、对索引0元素执行siftDown过程
             */
            data.swap(0, data.getSize() - 1);
            data.removeLast();
            siftDown(0);
            return t;
        }
    
        /**
         * 元素下沉操作(大值上浮,小值下沉)
         * 0、当该节点下是否具有左子节点:
         * 1、如果该节点存在具备右子节点,且右子节点大于左子节点,记录下右子节点索引
         * 2、如果不存在右子节点或右子节点小于左子节点,记录下左子节点索引
         * 3、此时记录下的索引值一定是最大值,与其父节点做比较,如果父节点小于该值,交换值并更新索引index
         */
        private void siftDown(int index) {
            //0
            while (leftChild(index) < data.getSize()) {
                int tag = leftChild(index);
                //1
                if (tag + 1 < data.getSize() && data.get(tag + 1).compareTo(data.get(tag)) > 0) {
                    tag ++;
                }
                //2、3 tag
                if(data.get(tag).compareTo(data.get(index)) > 0){
                    data.swap(tag,index);
                    index = tag;
                }
            }
        }

add和extractMax时间复杂度都是O(logn)，同二叉树的高度。因为堆是一个完全二叉树，永远不会退化成一个链表。

### replace ###

取出最大的元素后，再放入一个新的元素。

实现思路：①先执行一次extractMax的操作，再执行一次add操作，实际上是两次O(logn)的操作

②可以将堆顶的元素替换为新增元素，再调用一次siftDown，实际上是一次O(logn)操作

/**
         * 先取出堆中最大元素,再新增新元素
         * 将堆顶的元素替换为新增元素，再调用一次siftDown()
         */
        public T replace(T t){
            T t1 = findMax();
            data.add(0,t);
            siftDown(0);
            return t1;
        }

### heapify ###

将任意数组整理成堆的形状

①将给定的数组看成一个完全二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 8][]

②从最后一个非叶子节点开始下沉siftDown()，即从索引4位置不断向前执行siftDown()操作

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 9][]

plus：最后一个非叶子节点的索引为：获得最后一个索引，计算出其父节点索引。

对于索引从0开始的完全二叉树，其父节点索引为(data.getSize() - 1 ) / 2，从1开始为data.getSize() / 2

③索引4上的22小于其子节点(索引为9的62)，交换位置，下沉操作结束。再看索引为3所在节点，其左右节点最大值为41大于13，则41与13交换位置，下沉操作结束。再看索引为2所在节点，其左右节点最大值为28大于19，则28与19交换位置，下沉结束

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 10][]

④对于索引为1的节点17，它的最大子节点为62大于17，则62与17交换位置，此时17来到了索引为4的位置，由于17下还有子节点22且大于17，17与22交换位置，此时17来到了索引为9的位置。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 11][]

⑤索引为0的节点15，其最大子节点为62大于15，则15与62交换位置，此时15来到了索引为1的位置，由于其下面还有子节点，索引为1下的子节点最大值为41大于15，则41与15交换位置，此时15来到了索引为3的位置，由于其下面还有子节点，接着下沉索引为3下的子节点最大值为30大于15，30与15交换位置，此时15来到了索引为7的位置，由于索引为7不存在子节点，下沉结束。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 12][]

自此位置，heapify过程完成了，数组变成了一个最大堆。我们在heapfiy之前就排除了所有叶子节点，相当于一次抛弃了一半的节点，再进行siftDown操作，相比从一个空堆开始一个个添加元素要快很多(因为对每一个元素都要执行O(logn)的操作，相当于O(nlogn)级别的操作，**而heapify的过程，时间复杂度为0(n)级别**)

//Array类中
        public Array(E[] arr){
            data = (E[]) new Object[arr.length];
            for(int i = 0 ; i < arr.length ; i ++)
                data[i] = arr[i];
            size = arr.length;
        }

public MaxHeap(T[] arr){
            //构建一个完全二叉树
            data = new Array<>(arr);
            //从最后一个非叶子节点开始向前siftDown
            for(int i = parent(arr.length - 1) ; i >= 0 ; i--)
                siftDown(i);
        }

## 使用最大堆实现优先队列 ##

public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
        private MaxHeap<E> maxHeap;
        public PriorityQueue(){
            maxHeap = new MaxHeap<>();
        }
    
        public void enqueue(E e) {
            maxHeap.add(e);
        }
    
        public E dequeue() {
            return maxHeap.extractMax();
        }
    
        public E getFront() {
            return maxHeap.findMax();
        }
    
        public int getSize() {
            return maxHeap.getSize();
        }
    
        public boolean isEmpty() {
            return maxHeap.isEmpty();
        }
    }

## 优先队列的经典问题 ##

### 在100万元素中选出前100名 ###

即从N个元素中取出前M个元素【对应Leetcode 347题】

①如果通过先对100万元素排序，再取出前100个元素，使用高级排序算法可以达到**O(NlogN)**时间复杂度

②如果使用优先队列，可以达到**O(NlogM)**时间复杂度。实现思路：【使用优先队列，维护当前看到的前M个元素】如题中先取100万元素中索引为0-99的100个元素放入优先队列中，之后每个新的元素大于优先队列中最小的元素，则替换。直到扫描完100万个元素，最终留下来的元素则为前100名【**需要使用最小堆**】

/**
     * 从N个元素中取出出现频率最高的前k个元素
     * 实现思路:
     * 1、遍历数组,使用Map统计频次
     * 2、创建优先队列,当优先队列的大小小于k时，入队操作。
     *    当优先队列的大小大于k时，将优先队列中元素出现频率最少次数与新加入的元素比较
     *    如果即将入队元素频率大于优先队列中出现的最少频率，则最少频率的元素出队，新增元素入队替换
     * 3、创建LinkedList将优先队列的元素加入到链表中
     */
    public class Solution {
        private class Freq implements Comparable<Freq>{
            public int e , freq ;
    
            public int compareTo(Freq another) {
                if(this.freq < another.freq)
                    return 1;
                else if(this.freq > another.freq)
                    return -1;
                return 0;
            }
    
            public Freq(int e,int freq){
                this.e = e;
                this.freq = freq;
            }
        }
    
        public List<Integer> topKFrequent(int [] nums, int k){
    
            Map<Integer,Integer> map = new TreeMap<>();
            for(int num : nums){
                if(map.containsKey(num)){
                    map.put(num,map.get(num)+1);
                }else{
                    map.put(num,1);
                }
            }
            //执行完在queue中所剩的就是前k个元素 O(nlogk)
            PriorityQueue<Freq> queue = new PriorityQueue<>();
            for(int key : map.keySet()){
                if(queue.getSize() < k){
                    queue.enqueue(new Freq(key,map.get(key)));
                }
                else if(map.get(key) > queue.getFront().freq){
                    queue.dequeue();
                    queue.enqueue(new Freq(key,map.get(key)));
                }
            }
    
            LinkedList<Integer> linkedList = new LinkedList();
            while(!queue.isEmpty()){
                linkedList.add(queue.dequeue().e);
            }
            return linkedList;
        }
    }

plus: Java中的PriorityQueue为最小堆(小根堆)，使用Java内置的优先队列完成Leetcode

class Solution {
        public List<Integer> topKFrequent(int [] nums, int k){
    
            TreeMap<Integer,Integer> map = new TreeMap<>();
            for(int num : nums){
                if(map.containsKey(num)){
                    map.put(num,map.get(num)+1);
                }else{
                    map.put(num,1);
                }
            }
    
            //简化前
            PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
                public int compare(Integer a, Integer b) {
                    return map.get(a) - map.get(b);
                }
            });
    
    
            //可以使用Lambda表达式简化为:  简化后
            PriorityQueue<Integer> queue = new PriorityQueue<>(
                (a,b) -> map.get(a) - map.get(b)
            );
    
    
            for(int key : map.keySet()){
                if(queue.size() < k){
                    queue.add(key);
                }
                else if(map.get(key) > map.get(queue.peek())){
                    queue.remove();
                    queue.add(key);
                }
            }
    
            LinkedList<Integer> linkedList = new LinkedList();
            while(!queue.isEmpty()){
                linkedList.add(queue.remove());
            }
            return linkedList;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70]: /images/20220504/a9a139e7205c4a3f92c7e9fc73ab91c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 1]: /images/20220504/199f80402f7f4b269ea2ec896af27d34.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 2]: /images/20220504/88577b389c414ac293ae3aece2c955d1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 3]: /images/20220504/9b3a0070668742fabaaab0ee8ae21d7d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 4]: /images/20220504/27b4982a3e5b46f2a6b2f7577ef8ff74.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 5]: /images/20220504/84e2fe6a3e9a45f187424821cb1b008f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 6]: /images/20220504/269dbcdb5174439d8c15febecc0a7bb1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 7]: /images/20220504/72155171a7e84933b6173a6f6a47f29a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 8]: /images/20220504/8c454bf472a248adb234450745b9e7c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 9]: /images/20220504/37977426bafc415dae61bea33c776bec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 10]: /images/20220504/147bff4dffd948b8bdce591e25c09880.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 11]: /images/20220504/1add225dcb3248ee979a9b0935d771b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_27_color_FFFFFF_t_70 12]: /images/20220504/9c4714915a494f01aba7b069f91e04db.png