【Java数据结构】优先级队列详解（一）
1.❤️❤️前言~🥳🎉🎉🎉
Hello, Hello~ 亲爱的朋友们👋👋，这里是E绵绵呀✍️✍️。 如果你喜欢这篇文章，请别吝啬你的点赞❤️❤️和收藏📖📖。如果你对我的内容感兴趣，记得关注我👀👀以便不错过每一篇精彩。 当然，如果在阅读中发现任何问题或疑问，我非常欢迎你在评论区留言指正🗨️🗨️。让我们共同努力，一起进步！ 加油，一起CHIN UP！
2.优先级队列和堆的概念
我们都学过队列，队列是一种先进先出的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，这就是优先级队列。比如有时候我们在打游戏的时候，别人打电话给你，那么系统一定是先处理打进来的电话。
优先级队列其实也可以叫做堆 。 如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki 且 Ki= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做大根堆，根节点最小的堆叫做小根堆。 堆的性质： 堆中某个节点的值总是不大于或不小于其父节点的值； 堆总是一棵完全二叉树。
3.堆的存储
从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储。（底层为数组去存储）
注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。 将元素存储到数组中后，可以根据之前写的二叉树文章中的性质 对树进行还原。 假设i为节点在数组中的下标则有 1. 如果 i 为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2 2. 如果2 * i + 1 小于节点个数，则节点i存在左孩子下标，且为2 * i + 1，否则没有左孩子；如果2 * i + 2小于节点个数，则节点i存在右孩子下标，且为2 * i + 2，否则没有右孩子。
4.堆的模拟实现
4.1堆的成员变量和构造方法
其代码如下：
public class MyPriorityQueue {
int[] elem;
int usedSize;
public MyPriorityQueue() {
this.elem = new int[10];
}因为堆底层是数组，所以成员变量为两个。
一个是数组引用，另一个是堆存储的变量个数。
因为构造方法内部是elem指向一个长度为10的数组，所以创建该堆时，相当于创建了一个长度为10的数组。
4.2堆的向下调整方法——swapdown
向下调整算法（Heapify Down）是一种用于维护堆（最大堆或最小堆）性质的算法。当堆中的某个节点的值不满足堆性质（在最大堆中，每个节点的值都应大于或等于其子节点的值；在最小堆中，每个节点的值都应小于或等于其子节点的值）时，向下调整算法会将该节点向下移动，直到它满足堆性质。 向下调整算法通常用于以下场景： 当从堆中删除最大值（最大堆）或最小值（最小堆）时，通常将堆的最后一个元素移动到堆顶，然后进行向下调整，以重新满足堆的性质。 当初始化一个堆时，可以自底向上地对所有非叶子节点进行向下调整，以构建一个有效的堆结构。 向下调整算法的过程如下： 从不满足堆性质的节点开始，找到其子节点中的最大值（最大堆）或最小值（最小堆）。 如果当前节点的值小于（最大堆）或大于（最小堆）子节点中的最大值或最小值，则将当前节点与该子节点交换。 重复以上过程，直到当前节点满足堆的性质，或已经到达堆的底部。
//向下调整
public void swapDown(int[] elem,int i){
int parent=i;
int child=2*i+1;
while(child<=elem.length-1){
if(child+1<=elem.length-1&&elem[child]<elem[child+1]){
child=child+1;
}
if(elem[parent]<elem[child]){
int temp= elem[parent];
elem[parent]=elem[child];
elem[child]=temp;
parent=child;
child=child*2;
}
else
break;
}
}4.3堆的向上调整方法——swapup
向上调整算法（Heapify Up）是一种用于维护堆（最大堆或最小堆）性质的算法。当堆中的某个节点的值不满足堆性质（在最大堆中，每个节点的值都应大于或等于其子节点的值；在最小堆中，每个节点的值都应小于或等于其子节点的值）时，向上调整算法会将该节点向上移动，直到它满足堆性质。 向上调整算法通常用于以下场景： 当向堆中插入一个新元素时，通常将该元素添加到堆的末尾，然后进行向上调整，以重新满足堆的性质。 向上调整算法的过程如下： 从不满足堆性质的节点开始，找到其父节点。 如果当前节点的值大于（最大堆）或小于（最小堆）其父节点的值，则将当前节点与其父节点交换。 重复以上过程，直到当前节点满足堆的性质，或已经到达堆的顶部。 这种算法通过不断地将不满足堆性质的节点向上移动，直到找到合适的位置，从而维护了堆的性质。注意，向上调整算法在最坏情况下的时间复杂度为O(logn)，其中n是堆中元素的数量。 向上调整算法（Heapify Up）和向下调整算法（Heapify Down）都可以用于建堆，它们的时间复杂度有所不同。
public void swapUp(int[] elem,int i){
int parent=(i-1)/2;
int child=i;
while(child!=0){
if(elem[parent]<elem[child]){
int temp= elem[parent];
elem[parent]=elem[child];
elem[child]=temp;
child=parent;
parent=(child-1)/2;
}
else
break;
}
}4.4堆的创建——creatMyPriorityQueue
4.4.1向上调整方法建堆
向上调整方法建堆的过程是从一个空堆开始，依次将数组中的元素插入堆中。对于每个插入的元素，执行向上调整。在这个过程中，每个元素的向上调整最多需要O(logn)时间（其中n是堆中元素的数量），因为堆的高度是logn。
由二叉树的性质可以得知，每层结点的个数是2^(h-1)，在第几层的结点如果需要调整的话，最多需要向上调整h-1次。那么，调整次数将与高度相关，如下
因此，向上调整算法建堆的总时间复杂度为O(nlogn)。这是因为我们需要对n个元素执行向上调整操作，每个操作的时间复杂度为O(logn)。
4.4.2向下调整方法建堆
向下调整方法建堆的过程是当数组中的元素存储完毕后，再自底向上地对所有非叶子节点进行向下调整。从最后一个非叶子节点开始，依次向前遍历，对每个节点进行向下调整。
综上所述，向上调整算法建堆的时间复杂度为O(nlogn)，而向下调整算法建堆的时间复杂度为O(n)。在实际应用中，向下调整算法建堆通常比向上调整算法建堆更高效。
4.4.3创建大根堆
在堆的模拟实现中，我们模拟创建一个大根堆。
由上可知，我们是用向下调整方法去创建的，所以是自底向上地对所有非叶子节点进行向下调整。
代码如下：
public void creatMyPriorityQueue(int[] array){
for (int i = 0; i <array.length ; i++) {
if(usedSize==elem.length)
elem= Arrays.copyOf(elem,elem.length*2);
elem[i]=array[i];
usedSize++;
}
for (int i =usedSize-1/2 ; i >=0 ; i--) {
swapDown(elem,i);
}
}4.5.插入数据——offer
1.检查容量是否足够，不够的话需要扩容 2.将待插入的数据放在 usedSize 位置 3.从usedSize下标的数据向上调整 4.usedsize++
我们以大根堆举例：
假如99这个结点是新插入的,需要将该树的结构重新改为大根堆,那么需要进行向上调整,具体过程就是:依次从下往上跟它的父节点比较,如果大于父节点则交换 .
public void offer(int i){
if(usedSize==elem.length)
elem= Arrays.copyOf(elem,elem.length*2);
elem[usedSize]=i;
usedSize++;
swapUp( elem, usedSize-1);
}4.6删除数据——poll
出堆，出的是堆顶元素，即下标为0处的元素，因为对于数组来说，头删是十分不利的，因此我们这里学要借助一个小技巧： 1.将最后一个数据与堆顶数据进行交换 3.将堆中有效数据个数减少一个 2.然后再进行向下调整
切记poll删除的数据都是根节点的数据
public void poll(){
if(usedSize==0)
System.out.println("优先级队列中没有值");
int temp= elem[0];
elem[0]=elem[usedSize-1];
elem[usedSize-1]=temp;
usedSize--;
swapDown(elem,0);
}4.7获取栈顶元素——peek
太简单就不多说了，直接看代码
public int peek(){
if(usedSize==0)
System.out.println("优先级队列中没有值");
return elem[0];
}4.8 总代码及使用
public class MyPriorityQueue {
int[] elem;
int usedSize;
public MyPriorityQueue() {
this.elem = new int[10];
}
public void creatMyPriorityQueue(int[] array){
for (int i = 0; i <array.length ; i++) {
if(usedSize==elem.length)
elem= Arrays.copyOf(elem,elem.length*2);
elem[i]=array[i];
usedSize++;
}
for (int i =usedSize-1/2 ; i >=0 ; i--) {
swapDown(elem,i);
}
}
//向下调整
public void swapDown(int[] elem,int i){
int parent=i;
int child=2*i+1;
while(child<=elem.length-1){
if(child+1<=elem.length-1&&elem[child]<elem[child+1]){
child=child+1;
}
if(elem[parent]<elem[child]){
int temp= elem[parent];
elem[parent]=elem[child];
elem[child]=temp;
parent=child;
child=child*2;
}
else
break;
}
}
public void offer(int i){
if(usedSize==elem.length)
elem= Arrays.copyOf(elem,elem.length*2);
elem[usedSize]=i;
usedSize++;
swapUp( elem, usedSize-1);
}
//向上调整
public void swapUp(int[] elem,int i){
int parent=(i-1)/2;
int child=i;
while(child!=0){
if(elem[parent]<elem[child]){
int temp= elem[parent];
elem[parent]=elem[child];
elem[child]=temp;
child=parent;
parent=(child-1)/2;
}
else
break;
}
}
public void poll(){
if(usedSize==0)
System.out.println("优先级队列中没有值");
int temp= elem[0];
elem[0]=elem[usedSize-1];
elem[usedSize-1]=temp;
usedSize--;
swapDown(elem,0);
}
public int peek(){
if(usedSize==0)
System.out.println("优先级队列中没有值");
return elem[0];
}
}具体使用如下：
public class Test {
public static void main(String[] args) {
MyPriorityQueue myPriorityQueue=new MyPriorityQueue();
int[] array={10,4,6,8,9,5,-2,4,-1};
myPriorityQueue.creatMyPriorityQueue(array);
myPriorityQueue.offer(-4);
myPriorityQueue.offer(1);
myPriorityQueue.offer(50);
myPriorityQueue.offer(7);
myPriorityQueue.poll();
System.out.println(myPriorityQueue.peek());
myPriorityQueue.poll();
System.out.println(myPriorityQueue.peek());
}
}
5.总结
所以这篇文章我们就把堆的概念讲清楚了，并且模拟出来了堆，下篇文章将会正式使用priorityQueue。在此，我们诚挚地邀请各位大佬们为我们点赞、关注，并在评论区留下您宝贵的意见与建议。让我们共同学习，共同进步，为知识的海洋增添更多宝贵的财富！🎉🎉🎉❤️❤️💕💕🥳👏👏👏
腾讯云开发者
