Java優(yōu)先隊(duì)列(PriorityQueue)重寫compare操作
we can custom min heap or max heap by override the method compare.
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 class PriorityQueue {
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的排序不是普通的排序，而是堆排序，這有什么不同呢？來看下面一段代碼：
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)，如下：
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操作就是小編分享給大家的全部內(nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
- 解析Java中PriorityQueue優(yōu)先級(jí)隊(duì)列結(jié)構(gòu)的源碼及用法
- java優(yōu)先隊(duì)列PriorityQueue中Comparator的用法詳解
- Java數(shù)據(jù)結(jié)構(gòu)之優(yōu)先級(jí)隊(duì)列(PriorityQueue)用法詳解
- Java的優(yōu)先隊(duì)列PriorityQueue原理及實(shí)例分析
- Java中關(guān)于優(yōu)先隊(duì)列PriorityQueue的使用及相關(guān)方法
- Java中優(yōu)先隊(duì)列PriorityQueue常用方法示例
- Java優(yōu)先隊(duì)列PriorityQueue超全解析
相關(guān)文章
本文主要介紹了mybatis攔截器及不生效的解決方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04
Java實(shí)現(xiàn)定時(shí)任務(wù)的方法詳解
大家都用過鬧鐘，鬧鐘可以說是一種定時(shí)任務(wù)。那么，在?Java?中，如何實(shí)現(xiàn)這樣的功能呢？即如何實(shí)現(xiàn)定時(shí)任務(wù)呢？本文就來詳細(xì)和大家聊聊2022-10-10
SpringBoot動(dòng)態(tài)修改配置的十種方法
在SpringBoot應(yīng)用中,配置信息通常通過application.properties或application.yml文件靜態(tài)定義,應(yīng)用啟動(dòng)后這些配置就固定下來了,但我們常常需要在不重啟應(yīng)用的情況下動(dòng)態(tài)修改配置,本文將介紹SpringBoot中10種實(shí)現(xiàn)配置動(dòng)態(tài)修改的方法,需要的朋友可以參考下2025-05-05
這篇文章主要給大家介紹了關(guān)于Java8新特性：Lambda表達(dá)式之方法引用的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
別了Java EE! 正式更名為Jakarta，感興趣的小伙伴們可以參考一下2018-03-03
這篇文章主要介紹了Java多線程面試題(面試官常問),本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-03-03
Spring MVC InitBinder驗(yàn)證方法
這篇文章主要介紹了Spring MVC InitBinder驗(yàn)證方法，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-03-03
jEnv是一個(gè)命令行工具,正如它的官網(wǎng)所宣稱的那樣,它是來讓你忘記怎么配置JAVA_HOME環(huán)境變量的神隊(duì)友,這篇文章主要介紹了在macOS上安裝jenv管理JDK版本的詳細(xì)步驟,需要的朋友可以參考下2025-07-07
這篇文章主要介紹了Java并發(fā)編程之線程創(chuàng)建,進(jìn)程是代碼在數(shù)據(jù)集合上的一次運(yùn)行活動(dòng)，是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位，線程則是一個(gè)實(shí)體，一個(gè)進(jìn)程中至少有一個(gè)線程,下文更多相關(guān)內(nèi)容需要的小伙伴可以參考一下2022-04-04
本文主要介紹了idea在plugins中搜不到插件的解決方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-06-06