大家好,又见面了,我是你们的朋友全栈君。
一,概念
- 队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队列时,可能需要优先级高的元素先出队列
- 数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)
二,PriorityQueue的特性
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的
三,使用时的注意事项
1. 使用时必须导入PriorityQueue所在的包
import java.util.PriorityQueue;
2. PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出ClassCastException异常
3. 不能插入null对象,否则会抛出NullPointerException
4. 没有容量限制,可以插入任意多个元素,其内部可以自动扩容
5. 插入和删除元素的时间复杂度为
6. PriorityQueue底层使用了堆数据结构
7. PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素
四,PriorityQueue的构造器(三种)
import java.util.PriorityQueue;
public class MyPriorityQueue {
public static void method1(){
//不添加初始容量 默认为11
PriorityQueue<Integer> p1 = new PriorityQueue<>();
//添加初始容量为100
PriorityQueue<Integer> p2 = new PriorityQueue<>(100);
p1.offer(1);
p1.offer(2);
p1.offer(3);
p1.offer(4);
p1.offer(5);
//使用集合容器来进行构造
PriorityQueue<Integer> p3 = new PriorityQueue<>(p1);
System.out.println(p3.peek());
System.out.println(p3.size());
}
public static void main(String[] args) {
method1();
}
}
默认情况下,PriorityQueue队列是小堆,如果需要大堆需要用户提供比较器
public static void method2(){
PriorityQueue<Integer> p1 = new PriorityQueue<>();
p1.offer(10);
p1.offer(12);
p1.offer(14);
p1.offer(16);
p1.offer(18);
System.out.println(p1.peek());
PriorityQueue<Integer> p2 = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
p2.offer(10);
p2.offer(12);
p2.offer(14);
p2.offer(16);
p2.offer(18);
System.out.println(p2.peek());
}
五,插入/删除/获取优先级队列的元素以及使用
public static void method3(){
PriorityQueue<Integer> p = new PriorityQueue<>();
p.offer(1);
p.offer(2);
p.offer(3);
p.offer(4);
p.offer(5);
System.out.print(p.size() + " ");
System.out.println(p.peek());
p.poll();
p.poll();
System.out.print(p.size() + " ");
System.out.println(p.peek());
p.poll();
p.poll();
p.poll();
System.out.print(p.size() + " ");
System.out.print(p.peek() + " ");
System.out.println(p.poll() + " ");
if (p.isEmpty()){
System.out.println("p is empty!");
}else{
System.out.println("p is not empty!");
}
}
六,堆
1.什么是堆
JDK1.8中的PriorityQueue底层使用了堆的数据结构,而堆实际就是在完全二叉树的基础之上进行了一些元素的调整。
堆的性质:
- 堆中某个节点的值总是不大于或不小于其父节点的值;
- 堆总是一棵完全二叉树
2.堆的存储方式
堆是一棵完全二叉树,因此可以层序的规则采用顺序的方式来高效存储,
注意:对于非完全二叉树,则不适合使用顺序方式进行存储,因为为了能够还原二叉树,空间中须要存储空节点,就会导致空间利用率比较低
将元素存储到数组中后,可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标,则有:
- 如果i为0,则i表示的节点为根节点,否则i节点的双亲节点为 (i – 1)/2
- 如果2 * i + 1 小于节点个数,则节点i的左孩子下标为2 * i + 1,否则没有左孩子
- 如果2 * i + 2 小于节点个数,则节点i的右孩子下标为2 * i + 2,否则没有右孩子
3.堆的创建
向下调整
public void shiftDown(int[] array,int parent){
int child = parent * 2 + 1;
int size = array.length;
while(child < size){
if ((child + 1 < size) && (array[child + 1] < array[child])){
child = child + 1;
}
if (array[parent] <= array[child]){
break;
}else{
int temp = array[parent];
array[parent] = array[child];
array[child] = temp;
parent = child;
child = parent * 2 + 1;
}
}
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
堆的创建
//堆的创建
public void createHeap(int[] array){
int root = ((array.length - 2) >> 1);
for (int i = root; i >= 0 ; i--) {
shiftDown(array,root);
}
}
堆的插入与删除
向上调整
public void shiftUp(int child) {
// 找到child的双亲
int parent = (child - 1) / 2;
while (child > 0) {
// 如果双亲比孩子大,parent满足堆的性质,调整结束
if (array[parent] > array[child]) {
break;
}
else{// 将双亲与孩子节点进行交换
int t = array[parent];
array[parent] = array[child];
array[child] = t;
// 小的元素向下移动,可能到值子树不满足对的性质,因此需要继续向上调增
child = parent;
parent = (child - 1) / 1;
}
}
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/133261.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...