java优先级队列使用

桃扇骨 2023-10-18 14:45 40阅读 0赞

**优先级队列是比栈和队列更专用的结构，在多数情况下都非常有用。优先级队列像普通队列一样，有一个队头和队尾，并且也是从队头移除数据。**

优先级队列中，数据按关键词有序排列，插入新数据的时候，会自动插入到合适的位置保证队列有序。举个例子来说，一组整型数，如果使用优先级队列的话，不管队列之前放入的数据如何，后面添加进去的数据总会被按照升序或者降序排列，

当然这个只是优先级队列最基本的使用，在实际生产中可能有如下需求，

> 比方说我们有一个每日交易时段生成股票报告的应用程序，需要处理大量数据并且花费很多处理时间。客户向这个应用程序发送请求时，实际上就进入了队列。我们需要首先处理优先客户再处理普通用户

再举一个例子，

> 除了上面上面的场景，这里还给出一个这样的场景，比如一个电商网站搞特卖或抢购，用户登录下单提交后，考虑这个时间段用户访问下单提交量很大，通常表单提交到服务器后端后，后端程序一般不直接进行扣库存处理，将请求放到队列列，异步消费处理，用普通队列是FIFO的，这里有个需求是，用户会员级别高的，可以优先抢购到商品，可能这个时间段的级别较高的会员用户下单时间在普通用户之后，这个时候使用优先队列代替普通队列，基本能满足我们的需求。

PriorityQueue类在Java1.5中引入并作为 Java Collections Framework 的一部分。PriorityQueue是基于优先堆的一个无界队列，这个优先队列中的元素可以默认自然排序或者通过提供的Comparator（比较器）在队列实例化的时排序。  
优先队列不允许空值，而且不支持non-comparable（不可比较）的对象，比如用户自定义的类。优先队列要求使用Java Comparable和Comparator接口给对象排序，并且在排序时会按照优先级处理其中的元素。

优先队列的头是基于自然排序或者Comparator排序的最小元素。如果有多个对象拥有同样的排序，那么就可能随机地取其中任意一个。当我们获取队列时，返回队列的头对象。

优先队列的大小是不受限制的，但在创建时可以指定初始大小。当我们向优先队列增加元素的时候，队列大小会自动增加。  
PriorityQueue是非线程安全的，所以Java提供了PriorityBlockingQueue（实现BlockingQueue接口）用于Java多线程环境。

下面我们通过两段简单代码来体会一下优先级队列的使用，

1、使用优先级队列实现Integer类型数据自动排序，

//测试优先级队列自动排序
    	public static List<Integer> insertSort(){
    		List<Integer> list = new ArrayList<Integer>();
    		Queue<Integer> queue = new PriorityQueue<Integer>(7);
    		Random random = new Random();
    		for(int i=0;i<7;i++){
    			queue.add(new Integer(random.nextInt(100))); 
    		}
    		for(int i=0;i<queue.size();i++){
    			list.add(queue.poll());
    		}
    		return list;
    	}
    
    	public static void main(String[] args) {
    		System.out.println(Arrays.toString(insertSort().toArray()));
    	}

运行上述main函数，可以看到控制台打印出了排好序的结果，  
![在这里插入图片描述][20190221213503198.png]

优先级队列中，还提供了对对象的比较，下面我们来使用一下这个功能，

首先定义一个对象，

class Customer{
    	
    	private int id;
    	private String name;
    	
    	public int getId() {
    		return id;
    	}
    	public void setId(int id) {
    		this.id = id;
    	}
    	public String getName() {
    		return name;
    	}
    	public void setName(String name) {
    		this.name = name;
    	}
    	public Customer(int id, String name) {
    		super();
    		this.id = id;
    		this.name = name;
    	}
    	public Customer() {
    		super();
    	}
    	
    }

再实现一个通过ID进行对象比较的比较器，

//对象比较器
    	public static Comparator<Customer> idComparator = new Comparator<Customer>() {
    		public int compare(Customer o1, Customer o2) {
    			return (int)(o1.getId() - o2.getId());
    		}
    	};

//对象排序
    	public static void insertObjSort(){
    		Queue<Customer> queue = new PriorityQueue<Customer>(7,idComparator);
    		Random random = new Random();
    		for(int i=0;i<7;i++){
    			int id = new Integer(random.nextInt(100));
    			queue.add(new Customer(id,"name:" + i));
    		}
    		while(true){
    			Customer one = queue.poll();
    			if(queue.isEmpty()){
    				break;
    			}
    			System.out.println(one.getId() + " " + one.getName());
    		}
    		
    	}

同样，给出测试方法，

public static void main(String[] args) {
    		//System.out.println(Arrays.toString(insertSort().toArray()));
    		insertObjSort();
    	}

运行main函数，观察控制台输出结果，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70]

可以看到，通过优先级队列，我们实现了通过比较ID获得了对于对象比较的结果；

**本篇到此结束，感谢观看！**

[20190221213503198.png]: https://img-blog.csdnimg.cn/20190221213503198.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190221213822355.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw,size_16,color_FFFFFF,t_70