💕"哪里会有人喜欢孤独，不过是不喜欢失望。"💕
作者：Mylvzi
文章主要内容：数据结构之优先级队列(堆)
一.优先级队列
1.概念
我们已经学习过队列，队列是一种先进先出(FIFO)的数据结构，但是在有些情况下，数据的进出是有优先级的，优先级高的往往需要先"出"，优先级低的就需要后"出"，此时普通的队列就无法完成这样的操作(也就是数据在插入到队列中后，还需要根据优先级进行位置调整)，需要另外一种数据结构--优先级队列 PriorityQueue来实现
在实际生活中PriorityQueue的场景经常存在，比如你在打游戏的时候，如果有来电，系统应该优先处理来电。
在这种场景下，数据结构需要实现两个最基本的操作"返回优先级最高的对象"和"添加新的数据"
二.优先级队列的模拟实现
jdk1.8中的PriorityQueue 底层就使用了"堆"这种数据结构，堆实际上就是经过优先级调整的完全二叉树
注:这里的优先级在堆中的体现一般是所存储数据的大小
1.什么是堆？
堆是一种把元素按大小排列的完全二叉树，堆就是进行数据高效组织的另一种形式
从小到大排列：小根堆（每棵树的根节点的值比当前树的所有孩子都小）
从大到小排列：大根堆（每棵树的根节点的值比当前树的所有孩子都大）
大根堆示例:
小根堆示例:
2.堆的存储方式
堆其实是一颗完全二叉树，那么在存储的时候就可以使用顺序表进行数据的存储；而对于非完全二叉树来说，则不适合使用顺序表存储数据，因为会导致空间资源的浪费
既然是一颗完全二叉树，那就具有完全二叉树的一些性质
- 如果i为0，则i对应的结点是根节点；i的父节点的下标为(i-1)/2
- 由父节点的下标i可得左孩子的下标：2*i+1,右孩子的下标：2*i+2
3.堆的创建
一般都是根据数组去创建堆 使数组中的元素在二叉树中排列时呈现某种顺序
对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据，如果将其创建成堆呢？
观察集合，此时是无序的，我们需要通过调整将其设置为大根堆/小根堆
1.堆的实现
1.大根堆的实现
图解：
可见实现大根堆的核心思路在于"向下调整"，对已有的数据进行向下调整，使其符合规定的顺序
向下调整的步骤:
- 先获取到最后一棵子树的根节点的下标 parent = (usedSize - 1- 1)/2
- 获取到左右孩子结点的最大值(先获取左孩子，再判断左右孩子谁的值更大)
- 如果孩子节点的值>根节点的值，交换，交换之后需要堆parent重新赋值为child,继续向下调整
- 如果孩子节点的值<根节点的值，不交换，parent--;
对于2：为什么先获取左孩子的结点呢？因为对于一个完全二叉树来说，其最后一棵子树一定有左孩子，但是不一定有右孩子。
代码实现
// 根据传入的数组 将他们调整为大根堆 public int[] elem; public int usedSize; public TestHeap(int size) { this.elem = new int[size]; } // 初始化堆 public void initHeap(int[] arr) { for (int i = 0; i < arr.length; i++) { this.elem[i] = arr[i]; this.usedSize++; } } // 实现大根堆 /** * 从最后一棵子树的根节点开始，进行向下调整，一直调整到root */ // 向下调整 public void createHeap() { // 从最后一棵子树的根节点开始 for (int parents = (usedSize-1-1)/2; parents >= 0; parents--) { shiftDown(parents,usedSize); } } private void shiftDown(int parents, int usedSize) { // 先获取左孩子的下标 int child = 2*parents + 1; // 进行向下调整 while (child < usedSize) { // 先判断左右孩子的值是谁更大 if(child+1 < usedSize && elem[child] < elem[child+1]) { // 存在右孩子 且右孩子的值比左孩子的大 child++; } if(elem[child] > elem[parents]) { // 如果孩子结点的值比根节点大 交换 swap(child,parents); parents = child; child = 2*parents + 1; }else { // 如果根节点就是最大值 直接翻一下 break; } } } // 交换函数 private void swap(int i, int j) { int tmp = elem[i]; elem[i] = elem[j]; elem[j] = tmp; }
2.小根堆的实现
实现小根堆的逻辑是相同的，只需要在进行向下调整的时候改一下交换的逻辑
// 实现小根堆 public void createHeap2() { // 从最后一棵子树的根节点开始 for (int parents = (usedSize-1-1)/2; parents >= 0; parents--) { shiftDown(parents,usedSize); } } private void shiftDown2(int parents, int usedSize) { // 先获取左孩子的下标 int child = 2*parents + 1; // 进行向下调整 while (child < usedSize) { // 先判断左右孩子的值是谁更大 if(child+1 < usedSize && elem[child] > elem[child+1]) { // 存在右孩子 且右孩子的值比左孩子的小 child++; } if(elem[child] < elem[parents]) { // 如果孩子结点的值比根节点小 交换 swap(child,parents); // parent中大的元素向下移动 可能会造成子树不满足堆的性质 继续进行向下调整 parents = child; child = 2*parents + 1; }else { // 如果根节点就是最大值 break; } } }
向下调整的时间复杂度：
最坏的情况就是从根节点一直比到叶子节点，比较的次数就是完全二叉树的高度，O(logn)
其他情况比较的次数都是常数次，对于时间复杂度来说，一般只考虑最坏情况
2.堆的创建
在向下调整的代码中我们已经实现了堆的创建
// 堆的创建 public void createHeap() { // 从最后一棵子树的根节点开始 for (int parents = (usedSize-1-1)/2; parents >= 0; parents--) { shiftDown(parents,usedSize); } }
向下调整的时间复杂度是 O(logn)，那"建堆"的时间复杂度是多少呢？请看下面的推导
注:
1.堆建立的时间复杂度需要考虑两方面，每层的结点数，以及每个结点向下调整的最坏情况2.堆的时间复杂度的推导需要使用到数列中常见的一种方法"错位相减"
3.堆的时间复杂度一定要回手写推导，面试中有可能会考到！！！
3.在堆中添加元素
要求：添加之后仍满足大根堆的形式
说明：
- 在堆中插入一个新的元素之后，需要仍保持堆的性质，此时需要进行向上调整，直到调整到合适的位置；
- 由于堆的存储结构是一个顺序表，所以当顺序表满时，需要进行扩容 ；同时，堆的插入对应的就是顺序表的尾插
代码实现：
// 在堆内添加元素 /** * 插入到最后一个位置（保证是一个完全二叉树，且方便后续操作） * 向上调整 */ public void offer(int val) { if (isFull()) { this.elem = Arrays.copyOf(this.elem,2*this.elem.length); } this.elem[usedSize] = val; shiftUp(usedSize); this.usedSize++; } private void shiftUp(int child) { int parent = (child-1)/2; // == 0此时就是根节点了 不需要再去向上调整 // 需要一直调整到根节点 while(child != 0) { if(elem[child] > elem[parent]) { swap(child,parent); child = parent; parent = (child-1)/2; }else { break; } } } private boolean isFull() { return this.usedSize == this.elem.length; }
4.删除优先级最高的元素（数组的首元素）
堆的删除对应队列的"出队"操作，只不过堆的删除出的是优先级最高的元素
对于堆来说，优先级最高的元素位于堆顶，也就是顺序表的首元素，那如何进行堆的删除操作呢？
最直观的想法就是先保存堆顶元素，然后挪动堆顶元素之后的所有元素，使其都向前挪动一个位置，再对挪动之后的结果重新进行向下调整。这种方法实际上是可行的，但是时间复杂度过高，效率较低，这种方法的时间复杂度是挪动数据的时间复杂度O(n)与向下调整的时间复杂度O(logN)之和
当然还有另一种效率更高的实现方法，先交换堆顶和堆尾的元素，再进行向下调整，此方法的时间复杂度是交换的时间复杂度O(1)与向下调整的时间复杂度O(logN),效率明显比大量挪动数据更高
代码实现：
// 删除 一定是删除优先级最高的元素 最后返回优先级最高的那个元素 public int poll() { // 优先级最高的元素就是顺序表elem 的首元素 int tmp = elem[0]; swap(0,usedSize-1); this.usedSize--; // 只需对堆顶元素进行向下调整 shiftDown(0,usedSize); return tmp; }
注：
交换堆顶和堆尾元素这一操作还有另一考量，因为堆尾元素一定是优先级最低的元素，出队一定是最后一个进行出队，交换之后，堆顶是优先级最低的元素，就保证了其余元素都是优先级比堆顶元素更高，此时只需对堆顶元素进行向下调整即可，而不是从最后一棵子树的根节点开始进行调整
总结：删除堆中元素的三步骤
- 交换堆顶和堆中最后一个元素
- 删除最后一个元素
- 将堆顶元素进行向下调整
三.常用接口介绍
1.PriorityQueue的特性
Java的集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，此处主要介绍PriorityQueue
使用PriorityQueue的注意事项
- 需要导包，即：import java.util.PriorityQueue;
- PriorityQueue中存放的数据必须能够进行大小的比较，不能够插入无法比较的对象，否则会报错
PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>(); priorityQueue1.offer(1); priorityQueue1.offer(2); PriorityQueue<Student> priorityQueue2 = new PriorityQueue<>(); priorityQueue2.offer(new Student()); priorityQueue2.offer(new Student());// 报错
3.不能插入null，否则会报空指针异常
4.插入(向上调整)和删除的操作的时间复杂度都是O(logN)
5. PriorityQueue默认是小根堆，也就是根节点的值比子节点的值小
PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>(); priorityQueue1.offer(1); priorityQueue1.offer(2); priorityQueue1.offer(3); priorityQueue1.offer(4); priorityQueue1.offer(5); System.out.println(priorityQueue1.poll());// 输出1
数据结构之优先级队列(堆)及top-k问题讲解（二）+https://developer.aliyun.com/article/1413567
