数据结构之优先级队列【堆】（Heap）

旧城等待， 2023-09-28 15:17 80阅读 0赞

**目录**

1. 优先级队列（Priority Queue）

2.堆的概念

3.堆的存储方式

4.堆的创建

5.用堆模拟实现优先级队列

6.PriorityQueue常用接口介绍

6.1 PriorityQueue的特点

6.2 PriorityQueue几种常见的构造方式

7.top-k问题

8.堆排序

--------------------

**本篇主要内容总结**

> **（1）优先级队列底层是堆来实现的**
> 
> **（2）堆的本质是完全二叉树 ，堆有大根堆和小根堆**
> 
> **（3）大根堆：根节点最大的堆； 小根堆：根节点最小的堆**
> 
> **（4）堆的创建实现：大根堆为例**
> 
> **大根堆创建：孩子结点和根节点比较交换，核心思想：向下调整 时间复杂度O(n)**
> 
> **堆的插入：插入到最后一个位置，和根结点交换，核心思想：向上调整**
> 
> **堆的删除：只能删除堆顶，然后重新向下调整组成新的大根堆**
> 
> **插入和删除时间复杂度O（log n）**
> 
> **（4）priorityQueue建堆是小根堆，如果要建立大根堆就要写比较器**
> 
> **（5）priorityQueue添加元素，要写明比较的类型才能添加**
> 
> **（6）top-K问题：****前K个最大的元素建小根堆；前K个最小的元素建大根堆**
> 
> **第K个最大元素建小根堆 拿栈顶； 第K个最小元素建大根堆 拿栈顶**
> 
> **（7）堆排序：升序：大根堆 降序：小根堆**
> 
> **核心思想：堆元素的删除**

--------------------

**在说堆的概念之前，先说一下堆的常用方法，从这个方向来写这篇文章**

**堆的常用方法有**

**（1）用来构建优先级队列**

**（2）支持堆排序（大堆或小堆）**

**（3）top-k问题**

--------------------

## 1. 优先级队列（Priority Queue） ##

> **优先级队列 ：是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。**
> 
> **优先级队列相对于普通队列应该提供两个最基本的操作，**
> 
> **（1）返回最高优先级对象（2）添加新的对象**
> 
> **在JDk1.8中的优先级队列底层使用了堆**

## 2.堆的概念 ##

> **简单的说 ，堆这种数据结构本质上就是一个完全二叉树**
> 
> **并且堆中某个结点的值总是不大于或不小于其父结点的值**
> 
> **小堆：根节点最小的堆，满足Ki <= K2i+1 且 Ki <= K2i+2** 
> 
> **大堆：根节点最大的堆, 满足Ki >= K2i+1 且 Ki >= K2i+2** 
> 
> ![fc66ca1bc8f14726a728727992a95f0f.png][]

## 3.堆的存储方式 ##

> **堆是一颗完全二叉树，所以按照层序来看，可以采用顺序数组的存储方式**
> 
> **但是非完全二叉树就不适用于顺序存储了，这是因为非完全二叉树如果有空结点，那顺序存储也要存储这个空节点，这就造成空间上的浪费**
> 
> **i表示孩子结点，父亲结点（i-1）/ 2**
> 
> **i表示根节点 ，左孩子 2 \* i + 1 右孩子 2 \* i + 2**

## 4.堆的创建 ##

![3dd116db4f2b41aa94a4fca14b06e61a.png][]

## 5.用堆模拟实现优先级队列 ##

**按照大根堆来创建**

**先写一个数组，按顺序存储的方式**

public int[] elem;
        public int userSize;//当前堆中有效的元素数据个数
    
        public MyHeap() {
            this.elem = new int[10];
            this.userSize = 0;
        }
    
        public void initArray(int[] array) {
            elem = Arrays.copyOf(array,array.length);
            userSize = elem.length;
        }

**(1) 创建堆**

![5eb71b1306ba46b8a2d9da141027ad88.png][]

**先写一个向下调整的方法**

/**
         * @param parent: 每颗子树的根节点下标
         * @param len:每颗子树的结束位置
         * @description 向下调整
         */
        private void shiftDown(int parent,int len) {
            int child = 2*parent+1;//左孩子
            //必须要有左孩子
            while(child < len) {
                //如果一定有右孩子。那就判断 左孩子和右孩子大小，谁大保存谁
                if(child + 1 < userSize && elem[child] < elem[child+1]) {
                    child++;
                }
                //交换 比较孩子和根大小交换 然后根节点往下走继续必须
                if (elem[child] > elem[parent]) {
                    swap(elem,child,parent);
                    parent = child;
                    child = 2*parent+1;
                }else {
                    break;
                }
            }
        }

**再写一个交换根和孩子的方法**

//交换  比较孩子和根大小交换
        private void swap(int[] array, int i, int j) {
            int tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }

**然后通过循环每个结点，向下调整，然后创建好这棵树**

/**
         *建堆：大根堆
         *时间复杂度O(n)
         */
        public void createHeap() {
            for (int parent = (userSize-1-1)/2; parent >= 0 ; parent--) {
                shiftDown(parent,userSize);
            }
        }

**分析一下建堆的时间复杂度O(n)**

![035cab541ff242ee98930b6d318f0eb8.png][]

--------------------

**（2）堆的插入**

![106630c56c3c4e9ebd8f722234c9544a.png][]

**先写一个方法来判断空间满不满**

public boolean isFull() {
            return userSize == elem.length;
        }

**再写一个向上调整**

//向上调整
        private void shiftUp(int child) {
            int parent = (child - 1) / 2;
            while(child > 0) {
                if(elem[child] > elem[parent]) {
                    swap(elem,child,parent);
                    child = parent;
                    parent = (child - 1) / 2;
                }else {
                    break;
                }
            }
        }

**最后再写堆的插入，如果空间满了就扩容，然后再向上调整，变成新的大根堆**

//堆的插入
        public void offer(int x) {
            if (isFull()) {
                elem = Arrays.copyOf(elem,2*elem.length);
            }
            this.elem[userSize] = x;
            userSize++;
            shiftUp(userSize-1);
        }

**（3）堆的删除（优先级队列删除，只能删除堆顶的元素）**

![faa901edcaed4f5cb3a29a9643fecfa7.png][]

**再删除前，先要看堆是不是空的**

public boolean isEmpty() {
            return userSize == 0;
        }

**然后再删除堆顶元素**

//堆的删除  只能删除堆顶元素
        public int poll() {
            if (isEmpty()) {
                return -1;
            }
            int old = elem[0];
            //1.交换
            swap(elem,0,userSize-1);
            //2.有效元素个数-1
            userSize--;
            //3.栈顶元素向下调整
            shiftDown(0,userSize);
            return old;
        }

**看几个选择题把**

> **1.已知小根堆为8,15,10,21,34,16,12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较次数是**  **(C)** 
> 
> **A: 1 B: 2 C: 3 D: 4**

![78451fbebb4641d1835c5d3ad7bfb0e6.png][]

> 2.最小堆\[0,3,2,5,7,4,6,8\],在删除堆顶元素0之后，其结果是 () 
> 
> A: \[3 ， 2 ， 5 ， 7 ， 4 ， 6 ， 8\] B: \[2 ， 3 ， 5 ， 7 ， 4 ， 6 ， 8\] 
> 
> C: \[2 ， 3 ， 4 ， 5 ， 7 ， 8 ， 6\] D: \[2 ， 3 ， 4 ， 5 ， 6 ， 7 ， 8\]

![199291d18d36463aaec86fd8edc0f885.png][]

##  6.**PriorityQueue常用接口介绍**  ##

### **6.1 PriorityQueue的特点** ###

> **（1）首先最重要的先明白priorityQueue建堆是小根堆**

public static void main(String[] args) {
            //默认是小根堆
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
            priorityQueue.offer(45);
            priorityQueue.offer(12);
            priorityQueue.offer(55);
            priorityQueue.offer(66);
            System.out.println(priorityQueue.peek());
        }

![a72dcba124a24465a1132eaf7f5fc718.png][]

**可以看到这里打印的是12所以是priorityQueue是小根堆**

> **如果要建堆为大根堆，那就要写比较器Comparator了**

public static void main(String[] args) {
           PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
               @Override
               public int compare(Integer o1, Integer o2) {
                   return o2-o1;
               }
           });
        }

> **（2） 在priorityQueue使用offer添加元素时，一定要明确比较的规则，然后再添加**

**如果是直接这样比较的话，offer不知道以什么规则比较然后添加，就会报错。**

public static void main(String[] args) {
            PriorityQueue<Fruit> priorityQueue = new PriorityQueue<>();
            priorityQueue.offer(new Fruit() );
            priorityQueue.offer(new Fruit() );
        }

**所以这里必须告诉offer以什么方式比较添加，**

**比如说这里实现comparable接口**

class Fruit implements Comparable<Fruit>{
        public int age;
        //必须告诉priorityQueue.offer 以什么方式比较添加元素
        @Override
        public int compareTo(Fruit o) {
            return this.age - o.age;
        }
    }

> **（3）不能插入null对象，否则会抛出NullPointerException异常**

![999253febb6f4b919ecdc344394710cb.png][]

> **（4）可以插入任意多个元素，会自动扩容，没有容量限制**

![a5d464d8f32649749eab4439c0e255d6.png][]

>  **（5）插入和删除元素的时间复杂度为O(log n),建栈的时间复杂度O（n）**

--------------------

### 6.2 **PriorityQueue几种常见的构造方式** ###

> **（1）PriorityQueue() 初始默认容量为11**

![96ee9f6ba0d5413395ba4580a17a047d.png][]

> **（2）PriorityQueue(int initialCapacity)**

![72cb593c4d6a449e97aaa0a8ec089100.png][]

> **（3）PriorityQueue(Collection<? extends E> c)**

![6e5d867ab14d4729adc7746388965d85.png][]

> **（4）PriorityQueue(int initialCapacity, Collection<? super E> comparator**

--------------------

## 7.top-k问题 ##

> **适用情况，在数据量比较大时，求数据集合中前K个最大的元素或者最小的元素**

**比如说求很多个元素的前k个最大的元素**

**思路1：**

> **（1）将这些元素，全部放进大根堆中，堆顶的元素就是最大的值**
> 
> **（2）然后出k次，就能得到前k个最大的值，并且每出一次都会进行向下调整，变成新的大根堆**

public static void topK1(int[] array, int k) {
            PriorityQueue<Integer> maxPQ = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2-o1;
                }
            });
    
            for (int i = 0; i < array.length; i++) {
                maxPQ.offer(array[i]);
            }
            for (int i = 0; i < k; i++) {
                int val = maxPQ.poll();
                System.out.println(val);
            }
            System.out.println();
        }
        public static void main(String[] args) {
            int[] array = {16,15,22,155,89,12,45};
            topK1(array,3);
        }

![80a7a52e78fe4e2c9ffea8a1aa06f6a2.png][]

>  **缺点：数字有多少，这个堆就有多大，时间复杂度是O(n\*log n)**

**思路2：**

> **（1）求前K个最大的元素，建立大小为K的小根堆**
> 
> **（2）然后用剩下的集合里面的元素轮流和堆顶元素比较，如果剩下集合里面的元素比堆顶的元素大，那就替换掉堆顶的元素**
> 
> **（3）然后向下调整，变成新的小根堆，此时这个堆中的元素就是前K个最大元素**

![33b1ae2de2584418a899a25bf24ece0b.png][]

**1. 那如果要求前K个最小的元素，如何做**

> **差不多和前面一样的方法，不同的是**
> 
> **（1）求前K个最小的元素，要建立大根堆**
> 
> **（2）比较的时候谁小，就把小的放在堆顶**

力扣链接： [面试题 17.14. 最小K个数 - 力扣（LeetCode）][17.14. _K_ - _LeetCode]

class Solution {
        public int[] smallestK(int[] arr, int k) {
           int[] ret = new int[k];
            if(k == 0) return ret;
            PriorityQueue<Integer> maxPQ = new PriorityQueue<>(k,new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2-o1;
                }
            });
    
            for (int i = 0; i < arr.length; i++) {
                if(maxPQ.size() < k) {
                    maxPQ.offer(arr[i]);
                }else {
                    //获取到堆顶元素
                    int top = maxPQ.peek();
                    //找前k个最小的
                    if(arr[i] < top) {
                        maxPQ.poll();
                        maxPQ.offer(arr[i]);
                    }
                }
            }
            for (int i = 0; i < k; i++) {
                ret[i] = maxPQ.poll();
            }
            return ret;
        }
    }

**2. 那如果要求第K大的元素，或者第K小的元素如何做**

> **（1）前面求前K个最大的元素时，建立的小根堆，按照规则，到最后栈中全部都是前K个最大的元素，然后栈顶就是所要求得的第K大的元素**

> **（2）前面求前K个最小的元素时，建立的大根堆，按照规则，到最后栈中全部都是前K个最小的元素，然后栈顶就是所要求得的第K小的元素**

--------------------

## 8.堆排序 ##

**如果是将堆排成一个升序的，那就建立大根堆，操作如下**![3fea67680d0846ea83da338c292ee334.png][]

public void heapSort() {
            int end = userSize -1;
            while(end > 0) {
                swap(elem,0,end);
                shiftDown(0,end);
                end--;
            }
        }

![bdbb38503c6e4252bbe06e11e848572d.png][]

**如果是将堆排成一个降序的，那就建立小根堆，操作和上面类似**

> **一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为 (C)** 
> 
> **A: (11 5 7 2 3 17) B: (11 5 7 2 17 3) C: (17 11 7 2 3 5)** 
> 
> **D: (17 11 7 5 3 2) E: (17 7 11 3 5 2) F: (17 7 11 3 2 5)**

![59c271c4366b4524b36a93514717fa09.png][]

--------------------

[fc66ca1bc8f14726a728727992a95f0f.png]: https://img-blog.csdnimg.cn/fc66ca1bc8f14726a728727992a95f0f.png
[3dd116db4f2b41aa94a4fca14b06e61a.png]: https://img-blog.csdnimg.cn/3dd116db4f2b41aa94a4fca14b06e61a.png
[5eb71b1306ba46b8a2d9da141027ad88.png]: https://img-blog.csdnimg.cn/5eb71b1306ba46b8a2d9da141027ad88.png
[035cab541ff242ee98930b6d318f0eb8.png]: https://img-blog.csdnimg.cn/035cab541ff242ee98930b6d318f0eb8.png
[106630c56c3c4e9ebd8f722234c9544a.png]: https://img-blog.csdnimg.cn/106630c56c3c4e9ebd8f722234c9544a.png
[faa901edcaed4f5cb3a29a9643fecfa7.png]: https://img-blog.csdnimg.cn/faa901edcaed4f5cb3a29a9643fecfa7.png
[78451fbebb4641d1835c5d3ad7bfb0e6.png]: https://img-blog.csdnimg.cn/78451fbebb4641d1835c5d3ad7bfb0e6.png
[199291d18d36463aaec86fd8edc0f885.png]: https://img-blog.csdnimg.cn/199291d18d36463aaec86fd8edc0f885.png
[a72dcba124a24465a1132eaf7f5fc718.png]: https://img-blog.csdnimg.cn/a72dcba124a24465a1132eaf7f5fc718.png
[999253febb6f4b919ecdc344394710cb.png]: https://img-blog.csdnimg.cn/999253febb6f4b919ecdc344394710cb.png
[a5d464d8f32649749eab4439c0e255d6.png]: https://img-blog.csdnimg.cn/a5d464d8f32649749eab4439c0e255d6.png
[96ee9f6ba0d5413395ba4580a17a047d.png]: https://img-blog.csdnimg.cn/96ee9f6ba0d5413395ba4580a17a047d.png
[72cb593c4d6a449e97aaa0a8ec089100.png]: https://img-blog.csdnimg.cn/72cb593c4d6a449e97aaa0a8ec089100.png
[6e5d867ab14d4729adc7746388965d85.png]: https://img-blog.csdnimg.cn/6e5d867ab14d4729adc7746388965d85.png
[80a7a52e78fe4e2c9ffea8a1aa06f6a2.png]: https://img-blog.csdnimg.cn/80a7a52e78fe4e2c9ffea8a1aa06f6a2.png
[33b1ae2de2584418a899a25bf24ece0b.png]: https://img-blog.csdnimg.cn/33b1ae2de2584418a899a25bf24ece0b.png
[17.14. _K_ - _LeetCode]: https://leetcode.cn/problems/smallest-k-lcci/submissions/
[3fea67680d0846ea83da338c292ee334.png]: https://img-blog.csdnimg.cn/3fea67680d0846ea83da338c292ee334.png
[bdbb38503c6e4252bbe06e11e848572d.png]: https://img-blog.csdnimg.cn/bdbb38503c6e4252bbe06e11e848572d.png
[59c271c4366b4524b36a93514717fa09.png]: https://img-blog.csdnimg.cn/59c271c4366b4524b36a93514717fa09.png