we can custom min heap or max heap by override the method compare.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
package myapp.kit.quickstart.utils; import java.util.Comparator;import java.util.Queue; /** * priority queue (heap) demo. * * @author huangdingsheng * @version 1.0, 2020/5/8 */ public static void main(String[] args) { // min heap, process custom data struct Queue<Node> minHeap = new java.util.PriorityQueue<>(new Comparator<Node>(){ @Override public int compare(Node o1, Node o2) { return o1.v - o2.v; } }); // do sth... minHeap.add(new Node(1, 2)); minHeap.add(new Node(2, 9)); } // custom data struct static class Node { int k; int v; public Node(int k, int v) { this.k = k; this.v = v; } } } |
補(bǔ)充知識(shí)：Java中PriorityQueue的排序，堆排序
PrioriryQueue是Queue接口的一個(gè)隊(duì)列實(shí)現(xiàn)類，但它的排序并不是典型的隊(duì)列式先進(jìn)先出（FIFO）的方式。
PriorityQueue的排序方式分為兩種，一種是自然排序，這是按照加入元素的大小從小到大排序的。第二種是定制排序，是使用comparator類來重寫compare(Object o1,Object o2)方法來實(shí)現(xiàn)定制排序的。但是這些都不是關(guān)鍵，關(guān)鍵在于PriorityQueue的排序不是普通的排序，而是堆排序，這有什么不同呢？來看下面一段代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
import java.util.PriorityQueue;public class PriorityQueueTest3 { public static void main(String[] args) { PriorityQueue pq = new PriorityQueue(); pq.offer(6); pq.offer(-3); pq.offer(0); pq.offer(9); System.out.println(pq); }} |
輸出結(jié)果：[-3,6,0,9]
不是說是按從小到大來排序的嗎？怎么沒排序？
原因是堆排序只會(huì)保證第一個(gè)元素也就是根節(jié)點(diǎn)的元素是當(dāng)前優(yōu)先隊(duì)列里最小（或者最大）的元素，而且每一次變化之后，比如offer()或者poll()之后，都會(huì)進(jìn)行堆重排，所以如果想要按從小到大的順序取出元素，那么需要用一個(gè)for循環(huán)，如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
import java.util.PriorityQueue;public class PriorityQueueTest3 { public static void main(String[] args) { PriorityQueue pq = new PriorityQueue(); pq.offer(6); pq.offer(-3); pq.offer(0); pq.offer(9); int len = pq.size();//這里之所以取出.size()大小，因?yàn)槊恳淮蝡oll()之后size大小都會(huì)變化，所以不能作為for循環(huán)的判斷條件 for(int i=0;i<len;i++){ System.out.print(pq.poll()+" "); } System.out.println(); }} |
輸出 -3 0 6 9，按照從小到大的順序輸出的
以上這篇Java優(yōu)先隊(duì)列(PriorityQueue)重寫compare操作就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://blog.csdn.net/huangdingsheng/article/details/106010538
