备战蓝桥杯java(十二): 算法竞赛中的常用API:PriorityQueue(优先队列)
程序员文章站
2022-03-04 19:07:40
...
文章目录
PriorityQueue
翻译过来就是优先队列,本质是一个堆, 默认情况下堆顶每次都保留最小值,每插入一个元素,仍动态维护堆顶为最小值。
初始化
PriorityQueue()
//使用默认的初始容量(11)创建一个 PriorityQueue,并根据其自然顺序对元素进行排序。
PriorityQueue<Integer> Q = new PriorityQueue<>(); // 初始化
常用函数
add(E e)
//将指定的元素插入此优先级队列。clear()
//清空contains(Object o)
// 如果包含指定元素返回trueiterator()
//返回在此队列中的元素上进行迭代的迭代器。offer(E e)
// 将指定元素插入此优先队列peek()
// 获取第一个元素,及最小或最大元素poll()
// 获取并移除第一个remove(Object o)
// 移除指定元素size()
// 返回元素个数
实现大根堆的两种方式
- 使用自定义比较器
- 将所有数据变为之前自身的负数之后在插入, 因为添加个负号就相当于是逆序了嘛。1 < 2 < 3 取负之后变为 -1 > - 2 > - 3
实例
public static void main(String[] args){
Scanner in = new Scanner(new InputStreamReader(System.in));
PriorityQueue<Integer> Q = new PriorityQueue<>();
int a;
for(int i = 0; i < 10; i++){
a = in.nextInt();
Q.add(a);
System.out.print(Q.peek()+" ");// 输出当前队列的最小元素
}
}
输入: 1 -1 -2 -3 10 -4 -5 -6 -7 -8
输出: 1 -1 -2 -3 -3 -4 -5 -6 -7 -8