MinMaxPriorityQueue类介绍

青旅半醒 2021-06-24 16:00 559阅读 0赞

一、MinMaxPriorityQueue：

1、在guava包中有一个MinMaxPriorityQueue类，它提供了一种常数时间复杂度的方式访问其最小和最大元素的数据结构。作为一个queue，它在功能上和PriorityQueue一样。

1）在构造是可以指定比较器，如果没有指定那么使用自然排序。

2）要获得最少的元素，我们需要调用peekFirst（）方法。为了获得最大的元素，我们可以调用peekLast（）方法（这两个方法不会从队列中删除元素，它们只会检索它）。

MinMaxPriorityQueue<CustomClass> queue = MinMaxPriorityQueue
    				  .orderedBy(Comparator.comparing(CustomClass::getValue))
    				  .create();
    		
    		queue.add(new CustomClass(8));
    		queue.add(new CustomClass(18));
    		queue.add(new CustomClass(2));
    		queue.add(new CustomClass(6));
    		queue.add(new CustomClass(16));
    		
    		System.out.println(queue.peekFirst());
    		System.out.println(queue.peekLast());
    		
    		while (!queue.isEmpty()) {
    			CustomClass poll = queue.poll();
    			System.out.println(poll.getValue());
    		}

输出：

CustomClass \[value=2\]  
CustomClass \[value=16\]  
2  
5  
6  
8  
16

2、指定队列大小：

构造时可以指定MinMaxPriorityQueue的大小，这样，每次队列的大小超过该值时，队列将根据其比较器（可能是刚刚添加的元素）自动删除其最大元素。这与传统的有界队列不同，传统的有界队列在满时阻止或拒绝新元素。

注：根据MinMaxPriorityQueue的规范，如果队列已满，添加一个大于当前最大元素的元素将删除相同的元素，所以实际上会忽略这个操作。

MinMaxPriorityQueue<CustomClass> queue = MinMaxPriorityQueue
    				  .orderedBy(Comparator.comparing(CustomClass::getValue))
    				  .maximumSize(5)
    				  .create();
    		
    		queue.add(new CustomClass(8));
    		queue.add(new CustomClass(18));
    		queue.add(new CustomClass(2));
    		queue.add(new CustomClass(6));
    		queue.add(new CustomClass(16));
    		
    		System.out.println(queue.peekFirst());
    		System.out.println(queue.peekLast());
    		
    		queue.add(new CustomClass(5));
    		System.out.println("add 新元素");
    		System.out.println(queue.peekFirst());
    		System.out.println(queue.peekLast());
    		
    		while (!queue.isEmpty()) {
    			CustomClass poll = queue.poll();
    			System.out.println(poll.getValue());
    		}

输出：

CustomClass \[value=2\]  
CustomClass \[value=18\]  
add 新元素  
CustomClass \[value=2\]  
CustomClass \[value=16\]  
2  
5  
6  
8  
16

参考：

[https://www.baeldung.com/guava-minmax-priority-queue-and-evicting-queue][https_www.baeldung.com_guava-minmax-priority-queue-and-evicting-queue]

二、PriorityQueue：

PriorityQueue（优先队列）本质上是一个**最小堆**，是从JDK1.5开始提供的新的数据结构接口。不同于先进先出（FIFO）队列，每次从队列中取出的是具有最高优先权的元素（指定比较器）。

PriorityQueue<CustomClass> p = new PriorityQueue<CustomClass>(3,new Comparator<CustomClass>(){
    			@Override
    			public int compare(CustomClass o1, CustomClass o2) {
    				return o1.getValue()-o2.getValue();
    			}
    		});
    		p.add(new CustomClass(12));
    		p.add(new CustomClass(2));
    		p.add(new CustomClass(5));
    		
    		p.add(new CustomClass(15));
    		while (!p.isEmpty()) {
    			CustomClass poll = p.poll();
    			System.out.println(poll.getValue());
    		}

输出：

2  
5  
12  
15  
从这里我们可以看到，PriorityQueue在构造是第一个参数是initialCapacity，不是固定大小，我们可以不指定。

[https_www.baeldung.com_guava-minmax-priority-queue-and-evicting-queue]: https://www.baeldung.com/guava-minmax-priority-queue-and-evicting-queue