开发公司工程项目质量安全管理体系_无锡市网站搭建_盐城seo排名_开发一个平台需要多少钱

---

一、优先级队列是什么？

我们可以理解为，当我们需要将一个队列中优先级最高的(比如这个队列中最大的数，或者最小的数)出出来，这时候我们所要出的数就是我们优先级最高的数。比如在学校，老师在布置任务时会先找班长，班长不在，找团支书，再到学委等等，他们对于老师来说优先级是不一样的，我们要做的就是，知道这个最高优先级是谁，同时我们要在优先级最高的不在的情况(比如班长请假)，知道下一个优先级最高的人是谁，同时如果老师指定他所要的最高优先级人时要保持队列的优先级(让队列能存新的对象)，比如老师选了一个他的学科代表(凌驾所有人之上，那么它的优先级就要被放到最大)。

1.1 依靠堆来实现优先队列

堆是指按照二叉树的顺序存储方式来存储一组元素

堆分为大根堆和小根堆
大根堆是指，父亲节点是他孩子节点中的最大值

小根堆是指，父亲节点是他孩子节点中的最小值

注意：我们上图中展示到，不是大根堆所有的层的每个节点对于下面的层的每个节点都是从大到小的，比如下标为2的是32但下标为3的是31和4的是25，比它两个都大，大根堆只是保证一个节点的左右孩子比它小，同理小根堆也是。

---

1.2 堆的存储方式

堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储。
如果不是完全二叉树，说明数组中会有空的情况出现，对于空间的利用不高。

如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2。

如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子

如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子

如图，这个大根堆的数的个数为5，31的下标为1，它的左孩子为2 * 1 + 1，右孩子为2 * 1 + 2，12的下标为2，2 * 2 + 1 = 5,所以没有左孩子和右孩子。

1.3 堆的创建

1.3.1 建立大根堆

	public void createHeap(){//当数组个数小于2时说明，不需要建立if(usedSize < 2){return;}else if(usedSize == 2){//如果等于2，说明就两个数比较大小，大的放前面，只需要用到简单的交换if(array[0] < array[1]){swap(0,1);}}for(int parent = (usedSize - 2)/2; parent >= 0; parent--){shiftDown(parent);}}

---

1.3.2 向下排序

//向下排序private void shiftDown(int parent){int child = 2 * parent + 1;while (child < usedSize){if(child + 1 < usedSize && array[child] < array[child+1]){child++;}if(array[parent] < array[child]){swap(parent,child);parent = child;child = 2 * parent + 1;}else {break;}}}

---

1.3.3 添加元素

//添加元素public void offer(int val){if(array.length == usedSize){grow();}array[usedSize] = val;usedSize++;shiftup(usedSize);}

首先判断数组是否满了，然后将要添加的数组放到数组的尾巴，再将整个堆进行排序，这里用到的是向上排序，要注意的是先将usedSize++再排序，不然最后一个数无法排序。

---

1.3.4 向上排序

//向上排序private void shiftup(int child){int parent = (child - 1) / 2;while (parent >= 0){if(array[child] > array[parent]){swap(child,parent);child--;parent = (child - 1) / 2;}else {break;}}}

向上排序和向下的区别在于，向上建堆是从孩子节点向父亲节点，即是孩子在往前遍历，时间复杂度要比向下建堆高，因为底层的节点要一个一个遍历。

---

1.3.5 推出元素

//推出元素public Integer poll(){if(usedSize == 0){return null;}int val = array[0];array[0] = array[usedSize-1];array[usedSize - 1] = val;shiftDown(0);usedSize--;return val;}

每次推堆顶元素都要重新从堆顶进行重新的排序，保证大根堆，即班长走了，谁是老大。

---

1.3.6 查看堆顶元素

//查看堆顶元素public Integer peek(){if(usedSize == 0){return null;}return array[0];}

---

1.3.7 整个的代码实现

package demo1;import java.util.Arrays;public class MyPriorityQueue {public int[] array;public int usedSize;//数组中的数字个数//初始化数组长度public MyPriorityQueue() {this.array = new int[10];}//将数组拷入类中的数组，便于类中调用public void offerTheArray(int[] newarray){if(array.length < newarray.length){grow();}for (int i = 0; i < newarray.length; i++) {array[i] = newarray[i];usedSize++;}}//建立大根堆public void createHeap(){//当数组个数小于2时说明，不需要建立if(usedSize < 2){return;}else if(usedSize == 2){//如果等于2，说明就两个数比较大小，大的放前面，只需要用到简单的交换if(array[0] < array[1]){swap(0,1);}}for(int parent = (usedSize - 2)/2; parent >= 0; parent--){shiftDown(parent);}}//交换private void swap(int i,int j){int tmp = array[i];array[i] = array[j];array[j] = tmp;}//向下排序private void shiftDown(int parent){int child = 2 * parent + 1;while (child < usedSize){if(child + 1 < usedSize && array[child] < array[child+1]){child++;}if(array[parent] < array[child]){swap(parent,child);parent = child;child = 2 * parent + 1;}else {break;}}}//添加元素public void offer(int val){if(array.length == usedSize){grow();}array[usedSize] = val;usedSize++;shiftup(usedSize);}//向上排序private void shiftup(int child){int parent = (child - 1) / 2;while (parent >= 0){if(array[child] > array[parent]){swap(child,parent);child--;parent = (child - 1) / 2;}else {break;}}}//推出元素public Integer poll(){if(usedSize == 0){return null;}int val = array[0];array[0] = array[usedSize-1];array[usedSize - 1] = val;shiftDown(0);usedSize--;return val;}//查看堆顶元素public Integer peek(){if(usedSize == 0){return null;}return array[0];}//增长数组private void grow(){array = Arrays.copyOf(array,array.length*2);}}

二、优先级队列的使用

2.1 PriorityQueue的特性

1. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常。
2. 不能插入null对象，否则会抛出NullPointerException异常。
3. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容。
4. 插入和删除元素的时间复杂度为O(log2(N))。
5. PriorityQueue底层使用了堆数据结构。
6. PriorityQueue默认情况下是小根堆，即每次获取到的元素都是最小的元素。

2.2 PriorityQueue的实例化

以下解释来自AI

1. PriorityQueue()
   这是PriorityQueue的默认构造方法。它创建一个初始容量为 11 的优先队列，该队列根据元素的自然顺序进行排序（对于实现了Comparable接口的元素）。
   例如，如果你有一个实现了Comparable接口的Integer类型的优先队列，它会按照数字的大小进行排序。
2. PriorityQueue(int initialCapacity)
   这个构造方法允许你指定优先队列的初始容量。它创建一个具有指定初始容量的优先队列，同样根据元素的自然顺序进行排序。
   例如，如果你传入20作为参数，它会创建一个初始容量为 20 的优先队列。
3. PriorityQueue(Comparator<? super E> comparator)
   这个构造方法允许你传入一个自定义的比较器（Comparator）。它创建一个初始容量为 11 的优先队列，但使用你提供的比较器来确定元素的顺序，而不是元素的自然顺序。
   例如，如果你有一个自定义的Person类，并且你想按照年龄对Person对象进行排序，你可以创建一个Comparator并传入这个构造方法。
4. PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
   这个构造方法结合了前两个带参数的构造方法的功能。它允许你指定初始容量和自定义的比较器。
   例如，你可以创建一个初始容量为 30 且使用自定义比较器的优先队列。
5. PriorityQueue(Collection<? extends E> c)
   这个构造方法允许你使用一个现有的集合（Collection）来创建优先队列。它会按照元素的自然顺序进行排序，并将集合中的元素添加到优先队列中。
   例如，如果你有一个ArrayList，你可以使用这个构造方法将ArrayList中的元素转换为一个优先队列。
6. PriorityQueue(PriorityQueue<? extends E> c)
   这个构造方法允许你使用另一个优先队列来创建一个新的优先队列。它会复制另一个优先队列中的元素，并按照相同的顺序进行排序。
   例如，如果你有一个已经排好序的优先队列，你可以使用这个构造方法创建一个新的相同顺序的优先队列。
7. PriorityQueue(SortedSet<? extends E> c)
   这个构造方法允许你使用一个已排序的集合（SortedSet）来创建优先队列。它会按照集合中的顺序将元素添加到优先队列中。
   例如，如果你有一个TreeSet，你可以使用这个构造方法将TreeSet中的元素转换为一个优先队列。

什么是传比较器呢？

class intCmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
}
public class Test {public static void main(String[] args) {PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new intCmp());priorityQueue.offer(1);priorityQueue.offer(2);priorityQueue.offer(3);priorityQueue.offer(4);System.out.println(priorityQueue.poll());System.out.println(priorityQueue.poll());System.out.println(priorityQueue.poll());System.out.println(priorityQueue.poll());}
}

关于Comparator和Comparable我在java接口这篇博客有所介绍，有需要可以看看。

---

最后写个例题

例题最小k个数
我们建立大根堆，这个大根堆有k个数，为什么大根堆，因为大根堆的堆顶是最大的元素即第k小的数，如果有数比这个数小，说明这k个数不是最小的k个

class ImpCmp implements Comparator<Integer>{public int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}}
class Solution {public int[] smallestK(int[] arr, int k) {int[] array = new int[k];if(arr.length == 0 || k == 0){return array;}ImpCmp impCmp = new ImpCmp();PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k,impCmp);for(int i = 0; i < k; i++){priorityQueue.offer(arr[i]);}for(int i = k; i < arr.length;i++){if(arr[i] < priorityQueue.peek()){priorityQueue.poll();priorityQueue.offer(arr[i]);}}for(int i = 0; i < k; i++){int m = priorityQueue.poll();array[i] = m;}return array;}
}

---

总结

本篇博客主要介绍了有关优先队列的相关内容，如大根堆，小根堆，优先队列中，堆的模拟实现，和优先队列的相关使用，如果有什么不严谨不正确的地方，还望指正，谢谢大家！