Java数据结构——优先级队列
目录
一.什么是优先级队列
优先级队列是一种特殊的队列，它支持两种核心操作：
1.返回最高优先级对象
2.插入新的对象
与普通队列不同，优先级队列不是先进先出，而是高优先级的先出。如果优先级相同，则通常按插入顺序或元素自然顺序决定
二.堆——优先级队列的底层
在JDK1.8中，PriorityQueue的底层使用的是堆这种数据结构。堆本质上是一颗完全二叉树，并且其存储方式为顺序存储（即使用数组）。
2.1堆的定义与性质
对于集合K={……}，将其按完全二叉树的顺序存储在一维数组中。
小根堆：任意节点Ki<=K2i+1且Ki<=K2i+2
大根堆：任意节点KI>=K2i+1且Ki>=K2i+2
堆的两个重要性质：
堆中的某个节点的值总是不大于（或不小于）其父节点的值。
堆总是一个完全二叉树。
2.2堆的存储方式
由于的是完全二叉树，使用数组存储可以节省空间。对于下标为 i 的节点：
若 i==0，则为根节点
父节点：（i-1）/2
左孩子：2*i+1；右孩子：2*i+2
2.3堆的创建——向下调整
给定一个集合{27,15,19,18,28,34,65,49,25,37}，我们如何将它建成一个小根堆？如果根节点的左右子树已经满足堆性质，只需要将根节点向下调整到合适位置即可
向下调整法（以小根堆为例）：
1.用parent标记带调整节点，child标记其左孩子
2.如果child存在（child<size）,则：
找出左右孩子中较小的一个，用chilid标记
若array[parent]<=array[child],则调整结束。
否则，交换parent和child的值，然后继续向下：parent=child，child=2*parent+1
代码实现：
public void shiftDown(int[] arr,int parent){
int child=2*parent+1;
int size =arr.length;
while(child<size){
if(child+1<size&&arr[child]>arr[child+1]){
child++;
}
if(arr[parent]<=arr[child]){
break;
}
//交换
int temp=arr[parent];
arr[parent]=arr[child];
arr[child]=temp;
//继续向下
parent=child;
child=2*parent+1;
}
}建堆：如果整个树都不满足堆性质，需要从最后一个非叶子节点开始，向前依次向下调整
public static void createHeap(int[] arr){
int root=(arr.length-2)/2//最后一个非叶子节点下标
for(;root>=0;root--){
shiftDown(arr,root);
}
}时间复杂度：建堆的时间复杂度为O(N)
2.4堆的插入和删除
插入：
1.将元素放入数组末尾
2.从该节点开始向上调整，直到满足堆性质。
public void shiftUp(int child){
int parent=(child-1)/2;
while(child>0){
if(arr[parent]<=arr[child]){
break;
}
int temp=arr[parent];
arr[parent]=arr[child];
arr[child]=temp;
child=parent;
parent=(child-1)/2;
}
}删除（删除堆顶）
1.将堆顶元素与最后一个元素交换
2.有效元素个数减一
3.对新的堆顶执行向下调整
public class MyPriorityQueue {
private int[] array = new int[100]; // 简化，不考虑扩容
private int size = 0;
public void offer(int e) {
array[size++] = e;
shiftUp(size - 1);
}
public int poll() {
int oldValue = array[0];
array[0] = array[--size];
shiftDown(0);
return oldValue;
}
public int peek() {
return array[0];
}
// shiftDown 和 shiftUp 方法同上，此处省略
}注意：删除只能删除堆顶元素，这是优先级队列的特性。
三.Java中的PriorityQueue
java集合框架提供了PriorityQueue（线程不安全）和PriorityBlockingQueue（线程安全）
3.1使用注意：
1.必须导入包：import java.util.PriorityQueue;
2.元素必须可以比较哦啊，要么实现Comparable接口，要么构造时提供Comparator，否则抛出ClassCastException
3.不能插入null
4.无容量限制（内部自动扩容）
5.默认是小堆：每次取出都是最小元素，可以通过Comparator该为大堆
6.插入/删除时间复杂度O(logN)
3.2构造方法
| 构造器 | 说明 |
| PriorityQueue() | 默认容量为11 |
| PriorityQueue(int initialCapacity) | 指定初始容量 |
| PriorityQueue(Collection<? extends E> c) | 用已有集合构造 |
示例：
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 用集合构造
ArrayList<Integer> list = new ArrayList<>();
list.add(4); list.add(3); list.add(2); list.add(1);
PriorityQueue<Integer> pq2 = new PriorityQueue<>(list);
System.out.println(pq2.peek()); // 输出 1创建大堆：
class IntCmp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1; // 降序，大根堆
}
}
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new IntCmp());3.3常用方法
| 方法 | 说明 |
| boolean offer(E e) | 插入元素，失败抛异常 |
| E peek() | 获取堆顶元素（不删除） |
| E poll() | 移除并返回堆顶元素 |
| int size() | 元素个数 |
| void clear() | 清空 |
| boolean isEmpty() | 判空 |
3.4扩容机制
容量小于64，新容量=oldCapacity*2+2
容量大于64，新容量=oldCapacity+oldCapacity >>1
源码片段：
private void grow(int minCapacity) {
int oldCapacity = queue.length;
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow handling...
}四.堆排序
1.建堆：升序——>建大堆；降序——>建小堆
2.排序：将堆顶元素与末尾元素交换，堆大小减一，再向下调整
public static void heapSort(int[] arr) {
// 1. 建大堆
for (int i = (arr.length - 2) / 2; i >= 0; i--) {
shiftDownBig(arr, i, arr.length);
}
// 2. 交换 + 调整
int end = arr.length - 1;
while (end > 0) {
int temp = arr[0];
arr[0] = arr[end];
arr[end] = temp;
shiftDownBig(arr, 0, end);
end--;
}
}
// shiftDownBig 实现类似，注意比较符号相反时间复杂度：O(n Log n),空间：O(1),不稳定
总结：
优先级队列：一种按照优先级出队的抽象数据类型，底层通常使用堆实现
堆：一个完全二叉树，顺序存储，分为大根堆，小根堆
建堆:时间复杂度O(N)，利用向下调整；插入删除O(logN).
Java中PriorityQueue默认小堆，可自定义比较器变为大堆，注意元素必须可比较且不能为null
堆排序：不稳定排序，时间复杂度O(N logN)
更多推荐
3
0- 0
已为社区贡献20条内容
所有评论(0)