优先队列与堆
一、什么是优先队列与堆
优先级队列的底层实际上就是利用堆这种数据结构实现的。
堆在逻辑上是一棵完全二叉树，而其物理结构却是数组，二叉树中的每个节点对应着数组的下标，树中的第一个节点（根节点）的数组下标为0，树中的最后一个节点不一定为数组的最后一个元素（数组可能没满），而我们学习的堆，分为两种：
① 大顶堆：每个双亲节点的值都 >= 其左右孩子节点的值，此外，根节点的值一定是所有堆中其余节点的最大值。
② 小顶堆：每个双亲节点的值都 <= 其左右孩子节点的值，此外，根节点的值一定是所有堆中其余节点的最小值。
二、通过代码创建一个堆
说明一下：这里只是采用个人逻辑创建的一个堆，旨在与更深入地理解堆这个数据结构。
创建一个 .java 文件，里面放着一个类 Heap，通过 createHeap( ) 方法和 shiftDown( ) 来模拟一个堆。
public class Heap {
public int [] elem;
public int usedSize;
public Heap() {
this.elem = new int[10];
}
//创建一个堆
public void createHeap(int[] arr){
for (int i = 0; i < arr.length; i++) {
this.elem[i] = arr[i];
usedSize++;
}
for (int parent = ((usedSize-1)-1) / 2; parent >= 0 ; parent--) {
shiftDown(parent, usedSize);
}
}
//向下调整
public void shiftDown(int parent, int len){
int child = parent*2 +1 ;
while (child < len){
if(child+1 < len && elem[child] < elem[child+1]){
child++; //保证 child 走到左右最大的一个节点
}
if(elem[parent] < elem[child]){
int temp = elem[child];
elem[child] = elem[parent];
elem[parent] = temp;
}else {
break;
}
parent = child;
child = parent*2 +1 ;
}
}
//打印堆元素（层序）
public void print(){
for (int i = 0; i < usedSize; i++) {
System.out.print(elem[i] + " ");
}
System.out.println();
}
}
创建另一个 .java 文件，里面用主函数进行测试
public class Test {
public static void main(String[] args) {
int[] arr = {4,0,2,1,5,6,9,8,3,7};
Heap heap = new Heap();
System.out.println(Arrays.toString(arr));
heap.createHeap(arr);
System.out.println("-------------大顶堆-------------");
heap.print();
}
}
原始的堆：
优化成大顶堆：
输出结果：
在上述代码中，如果我们创建一个小顶堆，那么只需要更改几个不等号即可。
三、堆排序
一类问题：给定一组数据，将其按升序/逆序排序。
我们见过冒泡排序，但是本次我们通过堆排序进行操作。
举例，给定下列的数组 arr，让其升序排序
int[] arr = {4,0,2,1,5,6,9,8,3,7};
//排序后：0 1 2 3 4 5 6 7 8 9
堆排序思路：
① 在排序数组之前，我们要让数组符合大顶堆的逻辑
② 循环交换堆顶元素（即数组第一个元素）和堆尾元素（即数组最后一个元素），那么这样一来，数组的末尾逐渐排好
注意：每交换一次元素，我们就得重新让堆变成大顶堆逻辑，之后才能继续交换，这样做目的是：我们始终要让堆顶的元素处于最大值。
创建一个 .java 文件，里面放着一个类 Heap，通过 createHeap( ) 方法和 shiftDown( ) 来模拟一个堆，通过 heapSort( ) 进行堆排序
public class Heap {
public int [] elem;
public int usedSize;
public Heap() {
this.elem = new int[10];
}
//创建一个大顶堆
public void createHeap(int[] arr){
for (int i = 0; i < arr.length; i++) {
this.elem[i] = arr[i];
usedSize++;
}
for (int parent = ((usedSize-1)-1) / 2; parent >= 0 ; parent--) {
shiftDown(parent, usedSize);
}
}
//向下调整
public void shiftDown(int parent, int len){
int child = parent*2 +1 ;
while (child < len){
if(child+1 < len && elem[child] < elem[child+1]){
child++; //保证 child 走到左右最大的一个节点
}
if(elem[parent] < elem[child]){
int temp = elem[child];
elem[child] = elem[parent];
elem[parent] = temp;
}else {
break;
}
parent = child;
child = parent*2 +1 ;
}
}
public void heapSort(){
int end = usedSize-1;
while(end > 0){
int temp = elem[0];
elem[0] = elem[end];
elem[end] = temp;
end--;
shiftDown(0,end);
}
}
//打印堆元素（层序）
public void print(){
for (int i = 0; i < usedSize; i++) {
System.out.print(elem[i] + " ");
}
System.out.println();
}
}
创建另一个 .java 文件，里面用主函数进行测试
public class Test {
public static void main(String[] args) {
int[] arr = {4,0,2,1,5,6,9,8,3,7};
Heap heap = new Heap();
System.out.println(Arrays.toString(arr));
heap.createHeap(arr);
System.out.println("-------------创建一个大顶堆-------------");
heap.print();
System.out.println("-------------进行堆排序-------------");
heap.heapSort();
heap.print();
}
}
输出结果：
四、Java 实现的优先队列
我们来测试一下 Java 实现的优先级队列，并使用一些对应的方法：
可以发现 Java 集合框架中实现的优先级队列，它的底层实际上默认就是一个小顶堆。而我们不管使用了 offer( ) 方法，还是 poll( ) 方法，使用过后，Java 底层会自动将数组变换成小顶堆，也就是说：只要你向优先级队列中传入了数据，那么之后你所进行的所有操作，都只应用于小顶堆。
import java.util.PriorityQueue;
public class Test1 {
public static void main(String[] args) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(7);
System.out.println(priorityQueue);
priorityQueue.offer(3);
System.out.println(priorityQueue);
priorityQueue.offer(1);
System.out.println(priorityQueue);
priorityQueue.offer(5);
System.out.println(priorityQueue);
System.out.println(priorityQueue.size());
System.out.println(priorityQueue.peek());
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue);
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue);
System.out.println(priorityQueue.size());
}
}
输出结果：
1. 深度解析offer( ) 方法
这里的 offer( ) 方法采用了向上调整的逻辑，与我们之前的建堆逻辑不同，因为这里是从数组的尾部一个一个加进去的，通俗地说，就是先尾插，然后 Java 实现的优先级队列会自动为我们调整为小顶堆。
2. 深度解析poll( ) 方法
这里的 poll ( ) 方法并不是从数组的头部一个一个删除的，而是先将数组的第一个元素与数组的最后一个元素进行交换，之后进行调整。也就是说：我们每一次 poll 之后，底层就会帮我们调整为小顶堆。
下面是进行了优先队列的循环添加和循环删除，更好理解：
import java.util.PriorityQueue;
public class Test2 {
public static void main(String[] args) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
int[] arr = {4,2,5,6,0,9,1,8,3,7};
for (int i = 0; i < 10; i++) {
priorityQueue.offer(arr[i]);
System.out.println(priorityQueue);
}
System.out.println("----------------------------------");
for (int i = 0; i < 10; i++) {
priorityQueue.poll();
System.out.println(priorityQueue);
}
}
}
输出结果：
五、深度理解 Java 优先队列底层的代码
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Test1 {
public static void main(String[] args) {
//默认 优先级队列中的元素为11
PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
int [] arr1 = {4,0,2,1,5,6,9,8,3,7};
System.out.println(Arrays.toString(arr1));
for (int i = 0; i < arr1.length; i++) {
minHeap.offer(arr1[i]);
}
System.out.println("---------------小顶堆---------------");
System.out.println(minHeap);
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for (int i = 0; i < arr1.length; i++) {
maxHeap.offer(arr1[i]);
}
System.out.println("---------------大顶堆---------------");
System.out.println(maxHeap);
int k = 3;
PriorityQueue<Integer> maxHeap2 = new PriorityQueue<>(k,new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for (int i = 0; i < k; i++) {
maxHeap2.offer(arr1[i]);
}
System.out.println("---------------大顶堆---------------");
System.out.println(maxHeap2);
}
}
输出结果如下，关于使用 offer( ) 方法后，怎么进行调整为大顶堆/小顶堆，我已经通过上面两幅图说明的很清楚了。接下来我们一起来看看为什么我们要让堆实现内部类。
输出结果：
总结：
下面的这幅图是 Java 底层实现优先级队列的源码，当我们只看代码的时候，我要说明以下几点
① 在 PriorityQueue 类，当我们没有给定初始容量时，其默认容量为 11 ，当然我们也可以自己给定初始容量。
② 当我们不实现内部类，不传参的时候， PriorityQueue 类默认底层实现的是小顶堆。
③ 我们可以通过接口 Comparator，来重写 compare( ) 方法，以此来实现小顶堆或大顶堆。
小顶堆和大顶堆的语法格式
格式1
//默认为小顶堆，初始优先级队列的数组容量为11
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
格式2
为什么会出现格式2 这种形式？
在下面的代码块中，实际上我们并不是直接通过 Comparator 接口 new 了一个对象，而是通过匿名内部类实现了 Comparator 接口，并重写了 compare( ) 方法，这就是匿名内部类的语法。而这么做是为了更清楚地知道优先队列底层：堆这个数据结构是按什么比较的。
//小顶堆，初始优先级队列的数组容量为11
PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
格式3
在下面的格式中，我们可以看到，在 compare( ) 方法中，我们将 o2 和 o1 的位置调换过来了，对照格式2，我们就能清楚地明白，下面地程序是一个大顶堆地构造方式，因为大顶堆的堆顶永远是最大的元素。
//大顶堆，初始容量为3
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(3,new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
六、使用堆解决TopK问题
一类问题：给你一组数据，让你求这组数据中前 k 个最大的 / 最小的元素
举例题目：给你下面的一个数组 arr，求出其前三个最小的元素
int[] arr = {4,2,5,6,0,9,1,8,3,7};
//最小的三个元素 0,1,2
下面两个方法求的均是前 k 个最小的元素，当求前 k 个最大的元素逻辑其实是一样的，只是转换一下堆的使用即可。
方法一
- 创建一个大小为 3 的一个大顶堆
- 开始遍历数组
（1）前 k 个元素组建成大顶堆
（2）从 k+1 个元素开始，开始进行与堆顶判断
（3）如果新添加的元素 ＜ 堆顶的元素，那么就先头删，再尾插，过程中底层会自动帮我们调整大顶堆顺序 - 把前 k 个元素放入一个新的数组中，并返回给主函数
public class Test1 {
public static void main(String[] args) {
int[] arr = {4,2,5,6,0,9,1,8,3,7};
int k = 3;
int[] ret = topK(arr,k);
System.out.println(Arrays.toString(ret));
}
public static int[] topK(int[] arr, int k){
//1. 创建一个大小为 k 的一个大顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
//2. 开始遍历数组
for (int i = 0; i < arr.length; i++) {
//2.1 前 k 个元素组建成大顶堆
if(maxHeap.size() < k){
maxHeap.offer(arr[i]);
}else {
//2.2 从 k+1 个元素开始，开始进行与堆顶判断
int top = maxHeap.peek();
if(top > arr[i]){
maxHeap.poll();
maxHeap.offer(arr[i]);
}
}
}
//3. 把前 k 个元素放入一个新的数组中，并返回给主函数
int [] ret = new int[k];
for (int i = 0; i < k; i++) {
ret[i] = maxHeap.poll();
}
return ret;
}
}
输出结果：
方法二
- 创建一个小顶堆
- 将堆顶元素一个一个弹出至 ret 数组中
import java.util.Arrays;
import java.util.PriorityQueue;
public class Test1 {
public static void main(String[] args) {
int[] arr = {4,2,5,6,0,9,1,8,3,7};
int k = 3;
topK(arr,k);
}
public static void topK(int[] arr, int k){
//1. 创建一个小顶堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int i = 0; i < arr.length; i++) {
minHeap.offer(arr[i]);
}
System.out.println(minHeap);
int [] ret = new int[k];
//2. 将堆顶元素弹出至 ret 数组中
for (int i = 0; i < k; i++) {
ret[i] = minHeap.poll();
}
System.out.println(Arrays.toString(ret));
}
}
输出结果：
七、leetcode 373 查找和最小的K对数字
下面的两种方法就是使用我刚刚堆的性质来做的，主要我们需要理解一下思想
方法一
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
//1. 创建一个大顶堆
PriorityQueue<List<Integer>> maxHeap = new PriorityQueue<>(k, new Comparator<List<Integer>>() {
@Override
public int compare(List<Integer> o1, List<Integer> o2) {
return ( o2.get(0)+o2.get(1) ) - ( o1.get(0)+ o1.get(1) ) ;
}
});
//2. 遍历二维数组
for (int i = 0; i < Math.min(nums1.length,k); i++) {
for (int j = 0; j < Math.min(nums2.length,k); j++) {
//2.1 将前三个一维数组放入大顶堆中
if(maxHeap.size() < k){
List<Integer> list = new ArrayList<>();
list.add(nums1[i]);
list.add(nums2[j]);
maxHeap.offer(list);
}else{
//2.2 从第四个一维数组开始，与堆顶数组进行判断
int top = maxHeap.peek().get(0) + maxHeap.peek().get(1);
if( nums1[i] + nums2[j] < top){
maxHeap.poll();
List<Integer> list = new ArrayList<>();
list.add(nums1[i]);
list.add(nums2[j]);
maxHeap.offer(list);
}
}
}
}
List<List<Integer>> ret = new ArrayList<>();
for (int i = 0; i < k && !maxHeap.isEmpty() ; i++) {
ret.add(maxHeap.poll());
}
return ret;
}
}
为什么 for 循环的边界可以使用 Math.min( length, k) ？因为题目给出的原数组是两个升序的数组。
for (int i = 0; i < Math.min(nums1.length,k); i++) {
for (int j = 0; j < Math.min(nums2.length,k); j++) {
}
}
方法二
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
PriorityQueue<List<Integer>> minHeap = new PriorityQueue<>(k, new Comparator<List<Integer>>() {
@Override
public int compare(List<Integer> o1, List<Integer> o2) {
return (o1.get(0)+o1.get(1)) - (o2.get(0)+o2.get(1));
}
});
for (int i = 0; i < Math.min(nums1.length,k); i++) {
for (int j = 0; j < Math.min(nums2.length,k); j++) {
List<Integer> list = new ArrayList<>();
list.add(nums1[i]);
list.add(nums2[j]);
minHeap.offer(list);
}
}
List<List<Integer>> ret = new ArrayList<>();
for (int i = 0; i < k && !minHeap.isEmpty(); i++) {
ret.add(minHeap.poll());
}
return ret;
}
}
版权声明：本文为lfm1010123原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。