本节目标：
- 掌握堆的概念及实现
- 掌握 PriorityQueue 的使用
- 知道如何解决Topk问题
1.优先级队列
1.1 概念
众所周知，队列是一种先进先出（FIFO）的数据结构，但是有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要让优先级高的元素先出队列，在这种场景下，使用队列显然不合适。举个生活中的例子：我们在玩手机游戏时，如果有来电，那么手机系统就会优先处理打进来的电话。为了处理这种情况，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。所以优先级队列（Priority Queue）就来了！
在JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆又是在完全二叉树的基础上进行了一些调整，那么什么是堆呢？
如果有一个关键码的集合K = {k0, k1, k2, ... , k(n-1)}，把它的所有元素按完全二叉树的顺序储存方式存储在一个一维数组中，并满足：ki <= k2i + 1 且 ki <= k2i + 2，i = 0,1,2，… ，则称这个集合为小堆，相反如果是满足：ki >= k2i + 1 且 ki >= k2i + 2，i = 0,1,2，… ，则称这个集合为大堆。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。
堆的性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值。
- 堆总是一棵完全二叉树。
1.2 堆的存储方式
显而易见，堆是一颗完全二叉树，所以它可以采用层序遍历的规则采用顺式结构来高效存储。
从这个图可以看出，非完全二叉树不适合使用顺式结构进行存储，因为如果要还原非完全二叉树，空间中必须要存储空节点，这样就会导致空间利用率低。
1.3 堆的创建
假设现在有一个集合{27,15,19,18,28,34,65,49,25,37},怎么样把它变成一个堆呢？将这个集合放入一个数组中，按照层序遍历将它变为一棵完全二叉树如下：
观察上图，发现：根结点左右子树已经满足堆的性质（这里是小根堆），那么只需要将根结点向下调整即可！
堆的向下调整
向下调整需要用到根结点与左右孩子之间的关系：
如果将集合元素存到数组中，并且令i为结点在数组中的下标，那么根据二叉树的性质有：
- 如果i = 0，则表示的结点为根结点，否则可以求出 i 结点的双亲结点：(i - 1)/2。
- 如果2 * i + 1小于结点个数即数组有效元素个数size，则该结点的左孩子下标为：2 * i + 1，否则它没有左孩子。
- 如果2 * i + 2小于结点个数即数组有效元素个数size，则该结点的右孩子下标为：2 * i + 2，否则它没有右孩子。
这里以创建小根堆为例：
1.令parent标记需要调整的结点，child标记parent的左孩子（如果parent有孩子的话，一定是先有左孩子）
2.如果parent的的左孩子存在，即 child < size，那么进行以下操作，直至parent的左孩子不存在：
如果parent的有孩子存在，那么先找出左右孩子中最小的那一个，令child标记它。
将parent与child进行比较：如果parent小于child，不需要调整；否则交换parent与child，交换完成后，parent已经向下移动了，这时候可能会导致子树不满足堆的性质，所以还需要继续向下调整，即令parent = child，继续往下走，并且求出新的左孩子，child = 2 * parent + 1，继续进行 2。
由这个例子，我们发现：在调整以parent为根结点的二叉树时，这棵二叉树的左右子树必须满足已经是堆了才能进行向下调整。
向下调整的时间复杂度分析：这个例子就是最坏的情况，需要从根一路比较到叶子，比较的次数为这棵树的高度，那么时间复杂度为O(logN)。
通过代码实现向下调整如下：
public class MyHeap {
//初始数组容量为10
public int[] array = new int[10];
//数组有效元素个数
public int size;
//给定一个带参数初始化的构造方法
public MyHeap(int[] array) {
this.array = array;
this.size = array.length;
}
public MyHeap() {
}
//向下调整_建小根堆
public void siftDownToMinHeap(int parent) {
int child = 2*parent + 1;
while (child < this.size) {
//若右孩子存在,比较左右孩子的大小
if (child + 1 < this.size && this.array[child + 1] < this.array[child]) {
child = child + 1;
}
//如果child比parent的值还小，那么交换，符合小根堆
if (this.array[child] < this.array[parent]) {
swap(this.array,child,parent);
//parent继续向下走，防止这次交换后破坏堆结构
parent = child;
child = 2*parent + 1;
}else {
//符合堆结构就跳出循环，避免不必要的循环
break;
}
}
}
//交换两个数
private void swap(int[] arr,int i,int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
进行测试：
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = {27,15,19,18,28,34,65,49,25,37};
MyHeap myHeap = new MyHeap(arr);
myHeap.siftDownToMinHeap(0);
System.out.println(Arrays.toString(myHeap.array));
}
}
//运行结果
[15, 18, 19, 25, 28, 34, 65, 49, 27, 37]将得到的数组按层序遍历展开，确实是我们推算的结果！
这个例子中左右子树都是堆了，那对于左右子树都不是堆的情况呢？比如说一个普通集合{3,4,7,2,5,8}，又该如何调整呢？
其实也不难，既然需要左右子树都是堆才能向下调整根结点，那么先通过向下调整将左右子树变成根，最后再对根结点进行向下调整，这样子就行了，这里创建大根堆为例：
像这种左右子树都不满足堆的结构的，就和上述分析一样，先把左右子树调整为堆结构，再对根结点进行调整，要对左右子树进行调整，就需要找到左右子树中的非叶子结点，从最后一个非叶子结点开始，一步步走向树的根结点，而最后一个非叶子结点的下标可以由最后一个叶子结点的下标求得，设最后一个叶子结点的下标为 i ，那么最后一个非叶子结点的下标为(i - 1)/2。
代码实现如下：
//创建大根堆
public void createMaxHeap() {
//最后一个叶子结点的下标
int child = this.size-1;
//当parent == 0时，说明parent走到了树的根结点
for(int parent = (child - 1)/2; parent >= 0; parent--) {
//对每个非叶子结点进行向下调整
siftDownToMaxHeap(parent);
}
}
//向下调整_建大根堆
public void siftDownToMaxHeap(int parent) {
int child = 2*parent + 1;
while (child < this.size) {
//若右孩子存在,比较左右孩子的大小
if (child + 1 < this.size && this.array[child + 1] > this.array[child]) {
child = child + 1;
}
//如果child比parent的值还大，那么交换，符合大根堆
if (this.array[child] > this.array[parent]) {
swap(this.array,child,parent);
//parent继续向下走，防止这次交换后破坏堆结构
parent = child;
child = 2*parent + 1;
}else {
//符合堆结构就跳出循环，避免不必要的循环
break;
}
}
}进行测试：
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = {3,4,7,2,5,8};
MyHeap myHeap = new MyHeap(arr);
myHeap.createMaxHeap();
System.out.println(Arrays.toString(myHeap.array));
}
}
//运行结果
[8, 5, 7, 2, 4, 3]结果与我们画图分析的结果一致！
建堆的时间复杂度
由于堆是完全二叉树，而满二叉树也是完全二叉树的一种，因此为了简化求建堆的时间复杂度，这里使用满二叉树来证明（时间复杂度本就是看近似值的，所以多几个结点不影响最终结果）：
所以：建堆的时间复杂度为O(N)。
1.4 堆的插入与删除
堆的插入（使用向上调整）
当我们了解如何创建堆后，想要往堆里插入元素并不难，它只有两个步骤：
- 先将有效元素放入底层空间中（注意：当空间不够时，需要扩容）
- 然后将插入的结点向上调整，按照该结点到根结点的路径即可，直到这棵二叉树符合堆的性质
像这样：
按照这个思路，通过代码实现如下：
//向上调整_建立小根堆
public void siftUpMinHeap(int key) {
//判断数组满了没,满了进行扩容
if (this.size == this.array.length) {
this.array = Arrays.copyOf(array,2*array.length);
}
//将元素插入末尾
array[this.size] = key;
//此时插入元素的下标，即此时最后一个孩子的下标
int child = this.size;
siftUp(child);
this.size++;
}
//向上调整的逻辑部分
public void siftUp(int child) {
//找到它的双亲结点
int parent = (child - 1)/2;
//开始向上调整
while (child > 0) {
if (array[parent] > array[child]) {
//如果双亲结点的值大于孩子结点的值，那么交换，孩子结点往上调
swap(array,child,parent);
//交换完成后，继续向上调整，防止树还未符合堆的性质
child = parent;
parent = (child - 1)/2;
}else {
//如果此时检测到树已经符合堆的性质了，就退出循环
break;
}
}
}通过这个方法，我们插入两个元素试试，是不是能创建小根堆
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
MyHeap myHeap = new MyHeap();
myHeap.siftUpMinHeap(12);
myHeap.siftUpMinHeap(11);
int[] arr = myHeap.array;
System.out.println(Arrays.toString(arr));
}
}
//运行结果
[11, 12, 0, 0, 0, 0, 0, 0, 0, 0]确实是创建了小根堆（其他位置元素初始化默认为0）。
那么通过向上调整建堆的时间复杂度是多少呢？
因此通过向上调整建堆的时间复杂度是O(NlogN)。
堆的删除
我们所说的堆的删除删除的一定是堆顶元素！它的步骤通常如下：
- 将堆顶元素和堆中的最后一个元素交换
- 令堆中的有效元素个数-1
- 对此时的堆进行向下调整
像这样：
按照这个思路，代码如下：
//删除_维护小根堆
public int poll() {
int val = this.array[0];
swap(this.array,0,this.size-1);
this.size--;
siftDownToMinHeap(0);
//返回被删除元素
return val;
}进行测试：
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
MyHeap myHeap = new MyHeap();
myHeap.siftUpMinHeap(13);
myHeap.siftUpMinHeap(11);
myHeap.siftUpMinHeap(14);
myHeap.siftUpMinHeap(9);
System.out.println(Arrays.toString(myHeap.array));
int val = myHeap.pollToMinHeap();
System.out.println(Arrays.toString(myHeap.array));
System.out.println("被删除元素：" + val);
}
}
//运行结果
[9, 11, 14, 13, 0, 0, 0, 0, 0, 0]
[11, 13, 14, 9, 0, 0, 0, 0, 0, 0]
被删除元素：9
此时的9被移动到了有效元素的末尾，myHeap的size为3，并不会访问到9。
到此为止，关于优先级队列的底层，也就是堆的相关操作就全部手动实现了！至于删除维护大根堆、和向上调整建大根堆的操作方法，相信你已经可以写了，就算不可以也没事，完整代码如下：
import java.util.Arrays;
public class MyHeap {
//初始数组容量为10
public int[] array = new int[10];
//数组有效元素个数
public int size;
//给定一个带参数初始化的构造方法
public MyHeap(int[] array) {
this.array = array;
this.size = array.length;
}
public MyHeap() {
}
//向下调整_建小根堆
public void siftDownToMinHeap(int parent) {
int child = 2*parent + 1;
while (child < this.size) {
//若右孩子存在,比较左右孩子的大小
if (child + 1 < this.size && this.array[child + 1] < this.array[child]) {
child = child + 1;
}
//如果child比parent的值还小，那么交换，符合小根堆
if (this.array[child] < this.array[parent]) {
swap(this.array,child,parent);
//parent继续向下走，防止这次交换后破坏堆结构
parent = child;
child = 2*parent + 1;
}else {
//符合堆结构就跳出循环，避免不必要的循环
break;
}
}
}
//交换两个数
private void swap(int[] arr,int i,int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
//创建小根堆
public void createMinHeap() {
//最后一个叶子结点的下标
int child = this.size-1;
//当parent == 0时，说明parent走到了树的根结点
for(int parent = (child - 1)/2; parent >= 0; parent--) {
//对每个非叶子结点进行向下调整
siftDownToMinHeap(parent);
}
}
//创建大根堆
public void createMaxHeap() {
//最后一个叶子结点的下标
int child = this.size-1;
//当parent == 0时，说明parent走到了树的根结点
for(int parent = (child - 1)/2; parent >= 0; parent--) {
//对每个非叶子结点进行向下调整
siftDownToMaxHeap(parent);
}
}
//向下调整_建大根堆
public void siftDownToMaxHeap(int parent) {
int child = 2*parent + 1;
while (child < this.size) {
//若右孩子存在,比较左右孩子的大小
if (child + 1 < this.size && this.array[child + 1] > this.array[child]) {
child = child + 1;
}
//如果child比parent的值还大，那么交换，符合大根堆
if (this.array[child] > this.array[parent]) {
swap(this.array,child,parent);
//parent继续向下走，防止这次交换后破坏堆结构
parent = child;
child = 2*parent + 1;
}else {
//符合堆结构就跳出循环，避免不必要的循环
break;
}
}
}
//向上调整_建立小根堆
public void siftUpMinHeap(int key) {
//判断数组满了没,满了进行扩容
if (this.size == this.array.length) {
this.array = Arrays.copyOf(array,2*array.length);
}
//将元素插入末尾
array[this.size] = key;
//此时插入元素的下标，即此时最后一个孩子的下标
int child = this.size;
siftUpToMin(child);
this.size++;
}
//向上调整的逻辑部分
public void siftUpToMin(int child) {
//找到它的双亲结点
int parent = (child - 1)/2;
//开始向上调整
while (child > 0) {
if (array[parent] > array[child]) {
//如果双亲结点的值大于孩子结点的值，那么交换，孩子结点往上调
swap(array,child,parent);
//交换完成后，继续向上调整，防止树还未符合堆的性质
child = parent;
parent = (child - 1)/2;
}else {
//如果此时检测到树已经符合堆的性质了，就退出循环
break;
}
}
}
//向上调整_建立大根堆
public void siftUpMaxHeap(int key) {
//判断数组满了没,满了进行扩容
if (this.size == this.array.length) {
this.array = Arrays.copyOf(array,2*array.length);
}
//将元素插入末尾
array[this.size] = key;
//此时插入元素的下标，即此时最后一个孩子的下标
int child = this.size;
siftUpToMax(child);
this.size++;
}
//向上调整的逻辑部分
public void siftUpToMax(int child) {
//找到它的双亲结点
int parent = (child - 1)/2;
//开始向上调整
while (child > 0) {
if (array[parent] < array[child]) {
//如果双亲结点的值小于孩子结点的值，那么交换，孩子结点往上调
swap(array,child,parent);
//交换完成后，继续向上调整，防止树还未符合堆的性质
child = parent;
parent = (child - 1)/2;
}else {
//如果此时检测到树已经符合堆的性质了，就退出循环
break;
}
}
}
//删除_维护小根堆
public int pollToMinHeap() {
int val = this.array[0];
swap(this.array,0,this.size-1);
this.size--;
siftDownToMinHeap(0);
//返回被删除元素
return val;
}
//删除_维护大根堆
public int pollToMaxHeap() {
int val = this.array[0];
swap(this.array,0,this.size-1);
this.size--;
siftDownToMaxHeap(0);
//返回被删除元素
return val;
}
}
此代码供大家参考学习！
2.优先级队列类
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，这里主要学习PriorityQueue。
PriorityQueue所实现的接口和继承的类：
【注意】
- PriorityQueue中放置的元素必须能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常。
- 不能插入null对象，否则会抛出NullPointerException。
- 没有容量限制，可以插入任意多个元素，其内部可以自动扩容。
- 插入元素和删除元素的时间复杂度都是O(logN)。
- PriorityQueue默认情况下是创建小根堆。
PriorityQueue的方法
构造方法（常用）
| 构造方法 | 功能 |
|---|---|
| PriorityQueue() | 创建一个空的优先级队列，默认容量是11 |
| PriorityQueue(int initialCapacity) | 创建一个初始容量为initialCapacity的优先级队列，注意： initialCapacity不能小于1，否则会抛IllegalArgumentException异常 |
| PriorityQueue(Collection<? extends E> c) | 用一个集合来创建优先级队列 |
上面我们也说过了，PriorityQueue创建的是小根堆，如果我们要创建大根堆，就需要提供比较器。
首先，PriorityQueue的插入机制是这样的，如果队列中没有任何元素，就直接插入，如果有，就按照我们向上调整的思路，但是它不是简单的使用大于号和小于号进行比较，而是使用compare()方法进行比较！在没有传入比较器时，它的compare()方法调用compareTo()方法进行比较，即新元素.compareTo(该插入元素的双亲结点)，如果这个值为负，那么就进行交换，否则不换，也就是说它的底层逻辑是compare()方法的返回值为负就进行交换，那么我们想要创建大根堆，传入的比较器将会重写compare()方法，令compare()方法的值为负，使得新元素比该插入元素的双亲结点“小”！那么在这个重写的compare()方法中返回的是该插入元素的双亲结点.compareTo(新元素)的值即可，举个例子：
简单来说，就是要使新插入的元素看起来比插入元素的双亲结点“小”！
代码举例：
import java.util.Comparator;
import java.util.PriorityQueue;
//自定义大根堆比较器_比较的对象类型是Integer
class IntCmp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
}
public class Test {
public static void main(String[] args) {
PriorityQueue<Integer> queue = new PriorityQueue<>(new IntCmp());
queue.offer(4);
queue.offer(3);
queue.offer(2);
queue.offer(1);
queue.offer(5);
//查看堆顶元素
int val = queue.peek();
System.out.println(val);
}
}
//运行结果
5这时候创建出来的就是大根堆了！
其他的操作方法
| 方法 | 功能 |
|---|---|
| boolean offer(E e) | 插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时间复杂度O(logN)，注意：空间不够时候会进行扩容 |
| E peek() | 获取优先级最高的元素，如果优先级队列为空，返回null |
| E poll() | 移除优先级最高的元素并返回，如果优先级队列为空，返回null |
| int size() | 获取有效元素的个数 |
| void clear() | 清空 |
| boolean isEmpty() | 检测优先级队列是否为空，空返回true |
PriorityQueue的扩容机制
由于JDK17中对于PriorityQueue的一些方法进行了封装，对我们学习PriorityQueue的扩容机制不太友好，因此这里用JDK1.8的PriorityQueue扩容方式来解释：
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}简单来说就是：
- 如果容量小于64时，是按照oldCapacity的2倍方式扩容的
- 如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的
- 如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容
3.堆的应用
我们可以利用堆进行排序，也就是所谓的堆排序。要实现堆排序，有两个步骤：
1.建堆
根据我们的需要选择建大根堆还是小根堆，如果要所有元素升序排序，那么建大根堆；如果要降序排序，那么建小根堆。
2.利用堆删除的思想进行排序
具体操作如下图所示：
简单来说就是堆顶元素和堆尾元素，令最大的值“沉”到末尾，交换后堆的结构被破坏了，开始向下调整建新的堆，再重复交换和向下调整，不断缩小堆的范围（每次操作排除“沉”下去的末尾元素），当堆中仅剩一个有效元素时，那么就完成了堆排序，最终获得一个升序数组。(建小根堆实现降序数组的方式也同理)
代码实现如下：
//升序排序
public int[] heapSortRise() {
//建大根堆
createMaxHeap();
//进行排序操作
while (this.size > 1) {
//交换堆顶元素和堆尾元素
swap(this.array,0,this.size - 1);
//缩小范围
this.size--;
//从根结点开始对新的堆进行调整
siftDownToMaxHeap(0);
}
return this.array;
}进行测试：
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = {20,17,4,16,5,3};
MyHeap myHeap = new MyHeap(arr);
arr = myHeap.heapSortRise();
System.out.println(Arrays.toString(arr));
}
}
//运行结果
[3, 4, 5, 16, 17, 20]这是通过我们写的堆来实现的，那么通过PriorityQueue如何实现呢？其实更简单，PriorityQueue默认是创建小根堆，那么通过offer()方法将数组arr的元素全部插入后，将得到一个小根堆，那么我们再准备一个和arr一样大的数组，去接收PriorityQueue弹出的元素，最后就能得到一个升序的数组！像这样：
import java.util.Arrays;
import java.util.PriorityQueue;
public class Test {
public static void main(String[] args) {
int[] arr = {20,17,4,16,5,3};
PriorityQueue<Integer> queue = new PriorityQueue<>();
//将arr的元素全部插入优先级队列
for (int e:
arr) {
queue.offer(e);
}
//和arr一样大的数组
int[] ret = new int[arr.length];
//将优先级队列弹出的元素放到ret中
for (int i = 0; i < ret.length; i++) {
ret[i] = queue.poll();
}
System.out.println(Arrays.toString(ret));
}
}
//运行结果
[3, 4, 5, 16, 17, 20]学会堆排序后，就可以来处理Topk问题了！
4.Topk问题
TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如说：本专业前10名，游戏中前100的活跃玩家、世界富豪榜等等，这些都是Topk问题，对于这类问题，能想到的最简单直接的方法就是进行排序，可是如果数据量非常大的话，排序这种方法就不太行了，因为数据可能都不能一下子全部加载到内存中，面对这种情况，用堆来解决才是最佳方案，具体思路是这样的：
1.用数据集合中前k个元素建堆
- 求前k个最大的元素，就建小根堆
- 求前k个最小的元素，就建大根堆
2.用剩余的N-k个元素依次与堆顶元素，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
像这样：
简单来说，就是将前k个值建成小根堆，默认这k个值是数据中最大的，而堆顶元素是最大值中最小的那个，用它去和数据中剩余的值进行比较，如果剩余中的值比它大，就交换，再维护这个堆，使它始终为小根堆，堆顶元素始终是这k个最大值中最小的，如果剩余的值中，没有比堆顶元素大的，即没有比这k个最大值中最小值大的，就说明这k个值是前k个最大的！求前k个最小值也同理。
这里使用PriorityQueue来写代码实现：
import java.util.Arrays;
import java.util.PriorityQueue;
public class Test {
public static void main(String[] args) {
int[] arr = {2,11,3,22,1,8,91,21};
PriorityQueue<Integer> queue = new PriorityQueue<>();
//将前3个元素插入堆
for (int i = 0; i < 3; i++) {
queue.offer(arr[i]);
}
//用剩余的5个元素进行比较
for (int i = 3; i < arr.length; i++) {
//获取堆顶元素
int val = queue.peek();
if (arr[i] > val){
//将堆顶元素弹出
queue.poll();
//插入比较大元素
queue.offer(arr[i]);
}
}
//打印前3个最大值
for (int i = 0; i < 3; i++) {
System.out.print(queue.poll() + " ");
}
}
}
//运行结果
21 22 91 符合我们的预期！
到此，关于优先级队列PriorityQueue及其实现底层—堆的相关内容已经完结！感谢您的阅读，如有错误还请指出，谢谢！