算法竞赛中的常用JAVA API：PriorityQueue(优先队列)（转载）

时间：2024-01-03 14:40:08

算法竞赛中的常用JAVA API：PriorityQueue(优先队列)

PriorityQueue

翻译过来就是优先队列，本质是一个堆， 默认情况下堆顶每次都保留最小值，每插入一个元素，仍动态维护堆顶为最小值。

初始化

PriorityQueue()//使用默认的初始容量（11）创建一个 PriorityQueue，并根据其自然顺序对元素进行排序。

PriorityQueue<Integer> Q = new PriorityQueue<>(); // 初始化

常用函数

add(E e)//将指定的元素插入此优先级队列。

clear()//清空

contains(Object o) // 如果包含指定元素返回true

iterator()//返回在此队列中的元素上进行迭代的迭代器。

offer(E e) // 将指定元素插入此优先队列

peek() // 获取第一个元素，及最小或最大元素

poll() // 获取并移除第一个

remove(Object o) // 移除指定元素

size() // 返回元素个数

实现大根堆的两种方式

因为java中的优先队列默认是小根堆，要实现大根堆可以用以下两种方法：

  1. 使用自定义比较器

    如何用 PriorityQueue 实现大根堆 queueA？

    这里的知识点包括：

    • PriorityQueue 默认是小根堆，大根堆需要重写比较器。

    • 可以在 new PriorityQueue<>() 中的参数部分加入比较器。

    • 具体写法是：(v1, v2) -> v2 - v1。

    • Queue 类的输入是 offer() 方法，弹出是 poll() 方法。

      Queue<Integer> queueA = new PriorityQueue<>((v1, v2) -> v2 - v1);
      
queueA.offer(1);
      
queueA.poll();
      
queueA.size();
      A=new PriorityQueue<>(new Comparator<Integer>() {

			@Override
      
			public int compare(Integer o1, Integer o2) {
      
				// TODO 自动生成的方法存根
      
				return o2-o1;
      
			}
      
});


      PriorityQueue<Integer> pq=new PriorityQueue<>(Collections.reverseOrder());

  2. 将所有数据变为之前自身的负数之后在插入， 因为添加个负号就相当于是逆序了嘛。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

算法竞赛中的常用JAVA API：PriorityQueue(优先队列)（转载）

输入里面的那个是10是什么意思呀?

答：这个是小根堆， 每次输出堆中最小的元素， 输入10之后，最小的元素仍然是-3， 所以还是输出了-3

注： 转载参考

https://blog.csdn.net/qq_40525997/article/details/107846618

https://blog.csdn.net/qq_38522564/article/details/115029671

https://www.pianshen.com/article/84061294120/

https://blog.csdn.net/GD_ONE/article/details/104128985

相关文章