优先级队列概念
前面介绍过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)
PriorityQueue的特性
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue。
使用PriorityQueue注意事项：
- 使用PriorityQueue必须要导PriorityQueue所在的包
import.java.util.PriorityQueue;
- PriorityQueue所插入的元素必须要能比较大小，否则会抛出异常ClassCastExcepetion异常
- 不能插入null对象，否则会抛出NullPointerException
- 没有容量限制，可以插入任意个元素，会自动扩容
- 插入和删除元素的时间复杂度为 o(log2N)
- PriorityQueue底层使用了堆数据结构
优先级队列的构造
| 构造器 | 功能介绍 |
|---|---|
| PriorityQueue() | 创建一个空的优先级队列，默认容量是11 |
| PriorityQueue(int initialCapacity) | 创建一个初始容量为initialCapacity的优先级队列，注意：initialCapacity不能小于1，否则会抛IllegalArgumentExcepetion |
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
public class Demo {
public static void main(String[] args) {
//创建一个空的优先级队列，默认容量是11
PriorityQueue<Integer> q1 = new PriorityQueue<>();
//创建一个容量为100的空优先级队列
PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(5);
PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
System.out.println(q3.size());
System.out.println(q3.peek());
}
}
image.png
插入、删除、获取优先级最高的元素
| 函数名 | 功能介绍 |
|---|---|
| boolean offer(E e) | 插入元素，插入成功返回true，若e为null，会抛出NullPointerException异常，时间复杂度为O(log2N)，注意若空间不够会自动扩容 |
| E peek() | 获取优先级最高的元素，若队列为空，则返回null |
| E poll() | 移除优先级最高的元素，若队列为空，则返回null |
| int size() | 获取有效元素个数 |
| void clear() | 清空 |
| boolean isEmpty() | 检查优先级队列是否为空，若为空，则返回true |
package xsk;
import org.omg.CORBA.ARG_OUT;
import javax.sound.midi.Soundbank;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
public class Demo {
public static void main(String[] args) {
//创建一个空的优先级队列，默认容量是11
PriorityQueue<Integer> q1 = new PriorityQueue<>();
//创建一个容量为100的空优先级队列
PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(5);
PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
System.out.println(q3.size());
System.out.println(q3.peek());
q3.poll();
System.out.println(q3.size());
System.out.println(q3.peek());
q3.clear();
if(q3.isEmpty()) {
System.out.println("队列为空");
} else {
System.out.println("队列不为空");
}
q3.offer(1);
System.out.println(q3.peek());
System.out.println(q3.peek());
}
}
堆
堆是一种特殊的二叉树：
- 堆是一个完全二叉树
- 堆采用顺序存储的方式
-
堆中任一结点都满足比子节点的值大（大堆）或比子节点的值小（小堆）
我们来看一个大堆在内存的存储方式
image.png
image.png
从上图可以看出，父结点和子节点的关系：
已知父节点的下标为x,则孩子节点的下标：
- 左孩子下标：2 * x + 1;
- 右孩子下标：2 * x + 2;
已知孩子下标为x,则父节点的下标为：
- 左孩子下标为x 时，父节点的下标：( x - 1 ) / 2;
- 右孩子下标为x时，父节点的下标：( x - 1 ) / 2 或 ( x - 2 ) / 2;
堆的向下调整
image.png
仔细观察上图后发现：根节点的左右子树已经完全满足堆的性质，因此只需将根节点向下调整好即可。
向下过程(以小堆为例)：
- 1. 让parent标记需要调整的节点，child标记parent的左孩子(注意：parent如果有孩子一定先是有左孩子)
-
2. 如果parent的左孩子存在，即:child < size， 进行以下操作，直到parent的左孩子不存在：
- parent右孩子是否存在，存在找到左右孩子中最小的孩子，让child进行比较
-
将parent与较小的孩子child比较，如果：
* parent小于较小的孩子child，调整结束
* 否则：交换parent与较小的孩子child，交换完成之后，parent中大的元素
向下移动，可能导致子树不满足堆的性质，因此需要继续向下调整，即
parent = child; child = parent * 2 + 1;然后继续2的过程
向下调整（小堆）：
public void shiftDown(int[] arr, int size, int index) {
int parent = index;
int child = 2 * parent + 1;
while(child < size) {
if (child + 1 < size && arr[child + 1] < arr[child]) {
child = child + 1;
}
if(arr[parent] > arr[child]) {
int tmp = arr[child];
arr[child] = arr[parent];
arr[parent] = tmp;
} else {
break;
}
parent = child;
child = 2 * parent + 1;
}
}
}
注意：在调整以parent为根的二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整。
堆的创建
public static void createHeap(int[] array) {
// 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整
for(int i = arr.length - 1; i >= 0; i--) {
shiftDown(arr, arr.length, i);
}
}
堆的插入
插入堆需要两个步骤
- 先将元素放在底层空间中
-
将最后放入的元素向上调整，直到满足堆的性质
public class MyPriorityQueue {
public static void shiftUp(int[] arr, int size, int index) {
int child = index;
int parent = (child - 1) / 2;
while(child > 0) {
if(arr[child] > arr[parent]) {
int tmp = arr[child];
arr[child] = arr[parent];
arr[parent] = tmp;
} else {
break;
}
child = parent;
parent = (child - 1) / 2;
}
}
public static void creatHeap(int[] arr) {
for(int i = arr.length - 1; i >= 0; i--) {
shiftUp(arr, arr.length, i);
}
}
public int[] arr = new int[100];
public int size = 0;
public void offer(int val) {
if(size >= arr.length) {
return;
}
arr[size] = val;
size++;
shiftUp(arr, size, size - 1);
}
}
堆的删除
注意：堆删除的一定是堆顶元素，具体操作如下：
- 将堆顶元素与堆的最后一个元素交换
- 堆中有效数据个数减一
-
堆顶元素进行向下调整
image.png
public void poll(int val) {
if(size == 0) {
return;
}
int result = arr[0];
arr[0] = arr[size - 1];
arr[size - 1] = result;
size--;
shiftUp(arr, size, 0);
}
用堆实现优先级队列
package xsk;
public class MyPriorityQueue {
public static void shiftUp(int[] arr, int size, int index) {
int child = index;
int parent = (child - 1) / 2;
while(child > 0) {
if(arr[child] > arr[parent]) {
int tmp = arr[child];
arr[child] = arr[parent];
arr[parent] = tmp;
} else {
break;
}
child = parent;
parent = (child - 1) / 2;
}
}
public static void creatHeap(int[] arr) {
for(int i = arr.length - 1; i >= 0; i--) {
shiftUp(arr, arr.length, i);
}
}
public int[] arr = new int[100];
public int size = 0;
public void offer(int val) {
if(size >= arr.length) {
return;
}
arr[size] = val;
size++;
shiftUp(arr, size, size - 1);
}
public void poll(int val) {
if(size == 0) {
return;
}
int result = arr[0];
arr[0] = arr[size - 1];
arr[size - 1] = result;
size--;
shiftUp(arr, size, 0);
}
public Integer peek() {
if(size == 0) {
return null;
}
return arr[0];
}
}
