目录
前言:
1、PriorityQueue的特性
.2 PriorityQueue常用接口介绍
Ⅰ、PriorityQueue常见的构造方法
Ⅱ、常用的方法
Ⅲ、PriorityQueue的扩容方式:
3、应用
前言:
普通的队列是一种 先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。通常采用 堆数据结构来实现。在下面这篇文章中讲解了堆。八大排序之选择排序_冷兮雪的博客-CSDN博客
1、PriorityQueue的特性
Java 集合框架中提供了 PriorityQueue 和 PriorityBlockingQueue 两种类型的优先级队列, PriorityQueue 是线 程不安全的, PriorityBlockingQueue 是线程安全的 ,本文主要介绍 PriorityQueue 。
查看源码发现:PriorityQueue继承了AbstractQueue,并且初始容量为11,AbstractQueue又实现了Queue接口
关于PriorityQueue的使用要注意:
- 使用时必须导入PriorityQueue所在的包,即:
import java.util.PriorityQueue;
- PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出 ClassCastException异常
- 不能插入null对象,否则会抛出NullPointerException
- 没有容量限制,可以插入任意多个元素,其内部可以自动扩容
- 插入和删除元素的时间复杂度为log₂N
- PriorityQueue底层使用了堆数据结构,
- PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素(如果要设置为大根堆的话需要重写比较器来实现或者借助lambda表达式)
package 选择排序; import java.util.PriorityQueue; public class 优先级队列 { public static void main(String[] args) { PriorityQueue<Integer> queue=new PriorityQueue<>(); queue.offer(4); queue.offer(2); queue.offer(3); queue.offer(7); queue.offer(9); System.out.println(queue.peek());//2 } }
方法一:比较器
PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2-o1; } });
方法二:lambda表达式
Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
import java.util.Comparator;
import java.util.PriorityQueue;
public class 优先级队列 {
public static void main(String[] args) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(4);
queue.offer(2);
queue.offer(3);
queue.offer(7);
queue.offer(9);
System.out.println(queue.peek());//2
PriorityQueue<Integer> queue1=new PriorityQueue<>((o1, o2) -> o2-o1);
queue1.offer(4);
queue1.offer(2);
queue1.offer(3);
queue1.offer(7);
queue1.offer(9);
System.out.println(queue1.peek());//9
}
}
2 PriorityQueue常用接口介绍
Ⅰ、PriorityQueue常见的构造方法
构造器
|
解释 |
PriorityQueue()
|
创建一个空的优先级队列,默认容量是
11
|
PriorityQueue(int
initialCapacity)
|
创建一个初始容量为
initialCapacity
的优先级队列,注意:
initialCapacity不能小于1
,否则会抛
IllegalArgumentException
异 常
|
PriorityQueue(Collection<?
extends E> c)
|
用一个集合来创建优先级队列
|
import java.util.PriorityQueue;
class Student implements Comparable<Student>{
public int age;
@Override
public int compareTo(Student o) {//如果没有比较器,则下面添加时则会报错
return this.age-o.age;
}
}
public class 优先级队列 {
public static void main(String[] args) {
PriorityQueue<Student> queue=new PriorityQueue<>();
queue.offer(new Student());
queue.offer(new Student());
}
}
因为PriorityQueue不能插入无法比较大小的对象,需要实现比较器。
Ⅱ、常用的方法
Modifier and Type | Method and Description |
---|---|
boolean | |
add(E e) 将指定的元素插入到此优先级队列中。 | |
void |
clear() 从此优先级队列中册除所有元素。 |
Comparatore<? super E> | comparator( 返回用于为了在这个队列中的元素,或比较null如果此队列根据所述排序natural ordering的元素。 |
boolean | contains(object o) 如果此队列包含指定的元素,则返回true. |
Iteratore<E> | iterator() 返回此队列中的元素的迭代器。 |
boolean | offer(E e) 将指定的元素插入到此优先级队列中。 |
E | peek () 检素但不删除此队列的头,如果此队列为空,则返回null. |
E | poll() 检索并删除此队列的头,如果此队列为空,则返回null。 |
boolean | remove(object o) 从该队列中删除指定元素的单个实例(如果存在)。 |
int | size() 返回此集合中的元素数。 |
object[] | toArray() 返回一个包含此队列中所有元素的数组。 |
<T> T[] | toArray(T[]a) |
Ⅲ、PriorityQueue的扩容方式:
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
优先级队列的扩容说明:
- 如果容量小于64时,是按照oldCapacity的2倍方式扩容的
- 如果容量大于等于64,是按照oldCapacity的1.5倍方式扩容的
- 如果容量超过MAX_ARRAY_SIZE,按照MAX_ARRAY_SIZE来进行扩容
3、应用
经典优先级队列问题——TOP-K问题:最大或者最小的前k个数据
面试题 17.14. 最小K个数 - 力扣(Leetcode)
class Solution {
public int[] smallestK(int[] arr, int k) {
// 参数检测
if (null == arr || k <= 0)
return new int[0];
PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
// 将数组中的元素依次放到堆中
for (int i = 0; i < arr.length; ++i) {
q.offer(arr[i]);
}
// 将优先级队列的前k个元素放到数组中
int[] ret = new int[k];
for (int i = 0; i < k; ++i) {
ret[i] = q.poll();
}
return ret;
}
}
692. 前K个高频单词 - 力扣(Leetcode)
这题既可以使用HashMap也可以使用优先级队列。
优先级队列思想文章来源:https://www.toymoban.com/news/detail-434570.html
我们可以创建一个小根优先队列(顾名思义,就是优先队列顶端元素是最小元素的优先队列)。我们将每一个字符串插入到优先队列中,如果优先队列的大小超过了 k,那么我们就将优先队列顶端元素弹出。这样最终优先队列中剩下的 k个元素就是前 k 个出现次数最多的单词。文章来源地址https://www.toymoban.com/news/detail-434570.html
到了这里,关于优先级队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!