什么是PriorityQueue?
在Java中,PriorityQueue是一个基于优先级堆的无界优先队列。通过default natural ordering 或者通过一个实现了Comparable接口的比较器,元素会被按照升序排列(最小值在队头)。它不允许使用null元素,并且具有O(log n)插入和删除的时间复杂度。
如何往PriorityQueue中添加元素?
使用add()或offer()方法
PriorityQueue的add()方法和offer()方法都可以向队列中添加元素
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(3);
pq.offer(2);
以上代码演示了如何添加一个整型元素到PriorityQueue中。这样做会自动被排序为2, 3。
如何从PriorityQueue中获取元素?
使用poll()方法
poll()方法会从PriorityQueue中获取并移除队列头部元素,如果队列为空则返回null。
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(3);
pq.add(2);
System.out.println(pq.poll()); // 2
System.out.println(pq.poll()); // 3
System.out.println(pq.poll()); // null
如何在PriorityQueue中修改元素?
PriorityQueue本身是不支持对元素进行修改的,因为内部使用了堆数据结构,所以唯一能够修改PriorityQueue中元素的方法是先删除元素,再添加修改后的元素。
删除指定元素
在PriorityQueue中删除指定元素,可以使用remove(Object o)方法,返回true代表删除成功,false代表PriorityQueue中不存在该元素。
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(3);
pq.add(2);
pq.remove(3);
System.out.println(pq); // [2]
pq.remove(1);
System.out.println(pq); // [2]
以上代码演示了如何使用remove()方法删除一个指定元素,如果PriorityQueue中不存在该元素,remove()方法不会对PriorityQueue进行任何修改。
弹出并替换元素
在PriorityQueue中替换元素的通用方法是,先使用poll()方法删除元素,再用add()方法添加新元素。
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(3);
pq.add(2);
pq.poll();
pq.add(1);
System.out.println(pq); // [1, 3]
以上代码演示了如何在PriorityQueue中删除一个元素并且用另一个元素替换它。
如何在PriorityQueue中修改元素优先级?
修改元素优先级和修改元素的方法是类似的,先从PriorityQueue中删除该元素,然后修改该元素,在添加到PriorityQueue中。
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(3);
pq.add(2);
pq.poll();
pq.add(1);
pq.remove(3); //先删除,以下代码没有排序而直接add 3
pq.add(3);
System.out.println(pq); // [1, 3]
以上代码演示了如何在PriorityQueue中修改元素的优先级。
总结
在PriorityQueue中无法直接修改元素,但是可以通过删除元素再添加修改过后的元素,或者是删除元素再添加有相同值但不同优先级的元素的方法来实现。