本篇文章給大家?guī)?lái)了關(guān)于java的相關(guān)知識(shí)，在計(jì)算機(jī)科學(xué)中，堆(heap) 的實(shí)現(xiàn)是一種基于樹(shù)的特殊的數(shù)據(jù)結(jié)構(gòu)，它可以在數(shù)組上構(gòu)建出樹(shù)的結(jié)構(gòu)體，并滿足堆的屬性，下面就來(lái)聊聊Java數(shù)據(jù)結(jié)構(gòu)中的堆，感興趣的可以了解一下。

java代碼一鍵生成、拖拽設(shè)計(jì)：立即使用

推薦學(xué)習(xí)：《java視頻教程》

一、前言

堆的歷史

堆的數(shù)據(jù)結(jié)構(gòu)有很多種體現(xiàn)形式，包括；2-3堆、B堆、斐波那契堆，而在 Java API 中最常用的是用于實(shí)現(xiàn)優(yōu)先隊(duì)列的二叉堆，它是由 JWJ Williams 在 1964 年引入的，作為堆排序算法的數(shù)據(jù)結(jié)構(gòu)。另外在 Dijkstra 算法等幾種高效的圖算法中，堆也是非常重要的。

二、堆的數(shù)據(jù)結(jié)構(gòu)

在計(jì)算機(jī)科學(xué)中，堆(heap) 的實(shí)現(xiàn)是一種基于樹(shù)的特殊的數(shù)據(jù)結(jié)構(gòu)，它可以在數(shù)組上構(gòu)建出樹(shù)的結(jié)構(gòu)體，并滿足堆的屬性；

最小堆：如果P 是C 的一個(gè)父級(jí)節(jié)點(diǎn)， 那么P 的key(或value)應(yīng)小于或等于C 的對(duì)應(yīng)值。

最大堆：與最小堆的定義正好相反，最大堆(max heap) ,P 的key(或value)大于C 的對(duì)應(yīng)值。

三、堆的代碼實(shí)現(xiàn)

1. 實(shí)現(xiàn)介紹

堆的實(shí)現(xiàn)在 Java API 中主要體現(xiàn)在延遲隊(duì)列的實(shí)現(xiàn)二叉堆上，這里小傅哥單獨(dú)把這部分代碼拆分出來(lái)，了解下關(guān)于小堆和大堆的實(shí)現(xiàn)。

從對(duì)堆的數(shù)據(jù)結(jié)構(gòu)介紹上可以看到，小堆和大堆的唯一區(qū)別僅是對(duì)元素的排序方式不同。所以也就是說(shuō)在存放和獲取元素的時(shí)候?qū)υ氐奶畛浜驼龝r(shí)，排序方式不同而已。

2. 入堆實(shí)現(xiàn)

堆的在存放元素時(shí)，以遵循它的特點(diǎn)，會(huì)在存放過(guò)程中，通過(guò)隊(duì)尾元素向上比對(duì)遷移。

private void siftUpComparable(int k, E x) {     logger.info("【入隊(duì)】元素：{} 當(dāng)前隊(duì)列：{}", JSON.toJSONString(x), JSON.toJSONString(queue));     while (k > 0) {         // 獲取父節(jié)點(diǎn)Idx，相當(dāng)于除以2         int parent = (k - 1) >>> 1;         logger.info("【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：{} parent：{}", k, parent);         Object e = queue[parent];         // 如果當(dāng)前位置元素，大于父節(jié)點(diǎn)元素，則退出循環(huán)         if (compareTo(x, (E) e) >= 0) {             logger.info("【入隊(duì)】值比對(duì)，父節(jié)點(diǎn)：{} 目標(biāo)節(jié)點(diǎn)：{}", JSON.toJSONString(e), JSON.toJSONString(x));             break;         }         // 相反父節(jié)點(diǎn)位置大于當(dāng)前位置元素，則進(jìn)行替換         logger.info("【入隊(duì)】替換過(guò)程，父子節(jié)點(diǎn)位置替換，繼續(xù)循環(huán)。父節(jié)點(diǎn)值：{} 存放到位置：{}", JSON.toJSONString(e), k);         queue[k] = e;         k = parent;     }     queue[k] = x;     logger.info("【入隊(duì)】完成 Idx：{} Val：{} rn當(dāng)前隊(duì)列：{} rn", k, JSON.toJSONString(x), JSON.toJSONString(queue)); }

入堆的實(shí)現(xiàn) add 方法最終會(huì)調(diào)用到 siftUpComparable 方法，進(jìn)行排序的方式進(jìn)行處理。而這個(gè)排序 compareTo 方法是由具體的 MinHeap、MaxHeap 來(lái)做實(shí)現(xiàn)。

以入堆元素2舉例，如圖所示入堆過(guò)程。

首先將元素2掛到隊(duì)列尾部，之后通過(guò) (k – 1) >>> 1 計(jì)算父節(jié)點(diǎn)位置，與對(duì)應(yīng)元素進(jìn)行比對(duì)和判斷交換。

交換過(guò)程包括 2->6、2->5，以此交換結(jié)束后元素保存完畢。

3. 出堆實(shí)現(xiàn)

元素的出堆其實(shí)很簡(jiǎn)單，只要把根元素直接刪除彈出即可。但剩余接下里的步驟才是復(fù)雜的，因?yàn)樾枰诟剡w移走后，尋找另外的最小元素遷移到對(duì)頭。這個(gè)過(guò)程與入堆正好相反，這是一個(gè)不斷向下遷移的過(guò)程。

private void siftDownComparable(int k, E x) {     // 先找出中間件節(jié)點(diǎn)     int half = size >>> 1;     while (k < half) {         // 找到左子節(jié)點(diǎn)和右子節(jié)點(diǎn)，兩個(gè)節(jié)點(diǎn)進(jìn)行比較，找出最大的值         int child = (k << 1) + 1;         Object c = queue[child];         int right = child + 1;         // 左子節(jié)點(diǎn)與右子節(jié)點(diǎn)比較，取最小的節(jié)點(diǎn)         if (right < size && compareTo((E) c, (E) queue[right]) > 0) {             logger.info("【出隊(duì)】左右子節(jié)點(diǎn)比對(duì)，獲取最小值。left：{} right：{}", JSON.toJSONString(c), JSON.toJSONString(queue[right]));             c = queue[child = right];         }         // 目標(biāo)值與c比較，當(dāng)目標(biāo)值小于c值，退出循環(huán)。說(shuō)明此時(shí)目標(biāo)值所在位置適合，遷移完成。         if (compareTo(x, (E) c) <= 0) {             break;         }         // 目標(biāo)值小于c值，位置替換，繼續(xù)比較         logger.info("【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：{} 下節(jié)點(diǎn)：{} 位置替換", JSON.toJSONString(queue[k]), JSON.toJSONString(c));         queue[k] = c;         k = child;     }     // 把目標(biāo)值放到對(duì)應(yīng)位置     logger.info("【出隊(duì)】替換結(jié)果，最終更換位置。Idx：{} Val：{}", k, JSON.toJSONString(x));     queue[k] = x; }

不斷地向下遷移元素。這個(gè)過(guò)程會(huì)比對(duì)左右子節(jié)點(diǎn)的值，找到最小的。所以整個(gè)過(guò)程會(huì)比入堆麻煩一些。

這里以彈出元素1舉例，之后將堆尾元素替換到相應(yīng)的位置。整個(gè)過(guò)程分為6張圖表述。

• 圖1到圖2，找出根元素彈出。
• 圖3到圖4，將根元素向下遷移，與子元素比對(duì)，并替換位置。如果這個(gè)位置與8相比，小于8則繼續(xù)向下遷移。
• 圖4到圖5，繼續(xù)遷移，在原節(jié)點(diǎn)4的位置對(duì)應(yīng)的兩個(gè)子元素，都比8大，這個(gè)時(shí)候就可以停下來(lái)了。
• 圖5到圖6，更換元素位置，把隊(duì)尾的元素替換到對(duì)應(yīng)元素1向下遷移檢測(cè)的位置。

4. 小堆實(shí)現(xiàn)

小堆是一個(gè)正序比對(duì)

public class MinHeap extends Heap<Integer> {      @Override     public int compareTo(Integer firstElement, Integer secondElement) {         return firstElement.compareTo(secondElement);     }  }

測(cè)試

@Test public void test_min_heap() {     MinHeap heap = new MinHeap();     // 存入元素     heap.add(1);     heap.add(3);     heap.add(5);     heap.add(11);     heap.add(4);     heap.add(6);     heap.add(7);     heap.add(12);     heap.add(15);     heap.add(10);     heap.add(9);     heap.add(8);     // 彈出元素     while (heap.peek() != null){         logger.info("測(cè)試結(jié)果：{}", heap.poll());     } }

結(jié)果

17:21:30.053 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：3 當(dāng)前隊(duì)列：[1,null,null,null,null,null,null,null,null,null,null]
17:21:30.055 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：1 parent：0
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】值比對(duì)，父節(jié)點(diǎn)：1 目標(biāo)節(jié)點(diǎn)：3
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：1 Val：3
當(dāng)前隊(duì)列：[1,3,null,null,null,null,null,null,null,null,null]

17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：5 當(dāng)前隊(duì)列：[1,3,null,null,null,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：2 parent：0
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】值比對(duì)，父節(jié)點(diǎn)：1 目標(biāo)節(jié)點(diǎn)：5
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：2 Val：5
當(dāng)前隊(duì)列：[1,3,5,null,null,null,null,null,null,null,null]

17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：11 當(dāng)前隊(duì)列：[1,3,5,null,null,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：3 parent：1
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】值比對(duì)，父節(jié)點(diǎn)：3 目標(biāo)節(jié)點(diǎn)：11
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：3 Val：11
當(dāng)前隊(duì)列：[1,3,5,11,null,null,null,null,null,null,null]

17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：4 當(dāng)前隊(duì)列：[1,3,5,11,null,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：4 parent：1
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】值比對(duì)，父節(jié)點(diǎn)：3 目標(biāo)節(jié)點(diǎn)：4
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：4 Val：4
當(dāng)前隊(duì)列：[1,3,5,11,4,null,null,null,null,null,null]

17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：6 當(dāng)前隊(duì)列：[1,3,5,11,4,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：5 parent：2
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】值比對(duì)，父節(jié)點(diǎn)：5 目標(biāo)節(jié)點(diǎn)：6
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：5 Val：6
當(dāng)前隊(duì)列：[1,3,5,11,4,6,null,null,null,null,null]

17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：7 當(dāng)前隊(duì)列：[1,3,5,11,4,6,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：6 parent：2
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】值比對(duì)，父節(jié)點(diǎn)：5 目標(biāo)節(jié)點(diǎn)：7
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：6 Val：7
當(dāng)前隊(duì)列：[1,3,5,11,4,6,7,null,null,null,null] 17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：12 當(dāng)前隊(duì)列：[1,3,5,11,4,6,7,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：7 parent：3
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】值比對(duì)，父節(jié)點(diǎn)：11 目標(biāo)節(jié)點(diǎn)：12
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：7 Val：12
當(dāng)前隊(duì)列：[1,3,5,11,4,6,7,12,null,null,null]

17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：15 當(dāng)前隊(duì)列：[1,3,5,11,4,6,7,12,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：8 parent：3
17:21:30.056 [main] INFO queue.PriorityQueue – 【入隊(duì)】值比對(duì)，父節(jié)點(diǎn)：11 目標(biāo)節(jié)點(diǎn)：15
17:21:30.057 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：8 Val：15
當(dāng)前隊(duì)列：[1,3,5,11,4,6,7,12,15,null,null]

17:21:30.057 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：10 當(dāng)前隊(duì)列：[1,3,5,11,4,6,7,12,15,null,null]
17:21:30.057 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：9 parent：4
17:21:30.057 [main] INFO queue.PriorityQueue – 【入隊(duì)】值比對(duì)，父節(jié)點(diǎn)：4 目標(biāo)節(jié)點(diǎn)：10
17:21:30.057 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：9 Val：10
當(dāng)前隊(duì)列：[1,3,5,11,4,6,7,12,15,10,null]

17:21:30.057 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：9 當(dāng)前隊(duì)列：[1,3,5,11,4,6,7,12,15,10,null]
17:21:30.057 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：10 parent：4
17:21:30.057 [main] INFO queue.PriorityQueue – 【入隊(duì)】值比對(duì)，父節(jié)點(diǎn)：4 目標(biāo)節(jié)點(diǎn)：9
17:21:30.057 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：10 Val：9
當(dāng)前隊(duì)列：[1,3,5,11,4,6,7,12,15,10,9]

17:21:30.057 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：8 當(dāng)前隊(duì)列：[1,3,5,11,4,6,7,12,15,10,9,null,null,null,null,null,null,null,null,null,null,null,null,null]
17:21:30.057 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：11 parent：5
17:21:30.057 [main] INFO queue.PriorityQueue – 【入隊(duì)】值比對(duì)，父節(jié)點(diǎn)：6 目標(biāo)節(jié)點(diǎn)：8
17:21:30.057 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：11 Val：8
當(dāng)前隊(duì)列：[1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null,null,null,null,null,null,null,null]

17:21:30.057 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：1 下節(jié)點(diǎn)：3 位置替換
17:21:30.057 [main] INFO queue.PriorityQueue – 【出隊(duì)】左右子節(jié)點(diǎn)比對(duì)，獲取最小值。left：11 right：4
17:21:30.057 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：3 下節(jié)點(diǎn)：4 位置替換
17:21:30.057 [main] INFO queue.PriorityQueue – 【出隊(duì)】左右子節(jié)點(diǎn)比對(duì)，獲取最小值。left：10 right：9
17:21:30.057 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：4 Val：8
17:21:30.057 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：1
17:21:30.057 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：3 下節(jié)點(diǎn)：4 位置替換
17:21:30.057 [main] INFO queue.PriorityQueue – 【出隊(duì)】左右子節(jié)點(diǎn)比對(duì)，獲取最小值。left：11 right：8
17:21:30.057 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：4 下節(jié)點(diǎn)：8 位置替換
17:21:30.057 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：4 Val：9
17:21:30.057 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：3
17:21:30.057 [main] INFO queue.PriorityQueue – 【出隊(duì)】左右子節(jié)點(diǎn)比對(duì)，獲取最小值。left：8 right：5
17:21:30.057 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：4 下節(jié)點(diǎn)：5 位置替換
17:21:30.057 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：5 下節(jié)點(diǎn)：6 位置替換
17:21:30.057 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：5 Val：10
17:21:30.057 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：4
17:21:30.057 [main] INFO queue.PriorityQueue – 【出隊(duì)】左右子節(jié)點(diǎn)比對(duì)，獲取最小值。left：8 right：6
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：5 下節(jié)點(diǎn)：6 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】左右子節(jié)點(diǎn)比對(duì)，獲取最小值。left：10 right：7
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：6 下節(jié)點(diǎn)：7 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：6 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：5
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】左右子節(jié)點(diǎn)比對(duì)，獲取最小值。left：8 right：7
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：6 下節(jié)點(diǎn)：7 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：7 下節(jié)點(diǎn)：10 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：5 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：6
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：7 下節(jié)點(diǎn)：8 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】左右子節(jié)點(diǎn)比對(duì)，獲取最小值。left：11 right：9
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：8 下節(jié)點(diǎn)：9 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：4 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：7
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：8 下節(jié)點(diǎn)：9 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：9 下節(jié)點(diǎn)：11 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：3 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：8
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】左右子節(jié)點(diǎn)比對(duì)，獲取最小值。left：11 right：10
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：9 下節(jié)點(diǎn)：10 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：2 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：9
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：10 下節(jié)點(diǎn)：11 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：1 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：10
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：11 下節(jié)點(diǎn)：12 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：1 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：11
17:21:30.058 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：0 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：12
17:21:30.058 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：15

Process finished with exit code 0
小堆就是一個(gè)正序的輸出結(jié)果，從小到大的排序和輸出。
小堆空間：[1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null,null,null,null,null,null,null,null]

• 小堆就是一個(gè)正序的輸出結(jié)果，從小到大的排序和輸出。
• 小堆空間：[1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null,null,null,null,null,null,null,null]

5. 大堆實(shí)現(xiàn)

小堆是一個(gè)反序比對(duì)

public class MaxHeap extends Heap<Integer> {      @Override     public int compareTo(Integer firstElement, Integer secondElement) {         return secondElement.compareTo(firstElement);     }  }

測(cè)試

@Test public void test_max_heap() {     MaxHeap heap = new MaxHeap();     // 存入元素     heap.add(1);     heap.add(3);     heap.add(5);     heap.add(11);     heap.add(4);     heap.add(6);     heap.add(7);     heap.add(12);     heap.add(15);     heap.add(10);     heap.add(9);     heap.add(8);     // 彈出元素     while (heap.peek() != null){         logger.info("測(cè)試結(jié)果：{}", heap.poll());     } }

結(jié)果

17:23:45.079 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：3 當(dāng)前隊(duì)列：[1,null,null,null,null,null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：1 parent：0
17:23:45.081 [main] INFO queue.PriorityQueue – 【入隊(duì)】替換過(guò)程，父子節(jié)點(diǎn)位置替換，繼續(xù)循環(huán)。父節(jié)點(diǎn)值：1 存放到位置：1
17:23:45.081 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：0 Val：3
當(dāng)前隊(duì)列：[3,1,null,null,null,null,null,null,null,null,null]

17:23:45.081 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：5 當(dāng)前隊(duì)列：[3,1,null,null,null,null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：2 parent：0
17:23:45.081 [main] INFO queue.PriorityQueue – 【入隊(duì)】替換過(guò)程，父子節(jié)點(diǎn)位置替換，繼續(xù)循環(huán)。父節(jié)點(diǎn)值：3 存放到位置：2
17:23:45.081 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：0 Val：5
當(dāng)前隊(duì)列：[5,1,3,null,null,null,null,null,null,null,null]

17:23:45.081 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：11 當(dāng)前隊(duì)列：[5,1,3,null,null,null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：3 parent：1
17:23:45.081 [main] INFO queue.PriorityQueue – 【入隊(duì)】替換過(guò)程，父子節(jié)點(diǎn)位置替換，繼續(xù)循環(huán)。父節(jié)點(diǎn)值：1 存放到位置：3
17:23:45.081 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：1 parent：0
17:23:45.081 [main] INFO queue.PriorityQueue – 【入隊(duì)】替換過(guò)程，父子節(jié)點(diǎn)位置替換，繼續(xù)循環(huán)。父節(jié)點(diǎn)值：5 存放到位置：1
17:23:45.081 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：0 Val：11
當(dāng)前隊(duì)列：[11,5,3,1,null,null,null,null,null,null,null]

17:23:45.081 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：4 當(dāng)前隊(duì)列：[11,5,3,1,null,null,null,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：4 parent：1
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】值比對(duì)，父節(jié)點(diǎn)：5 目標(biāo)節(jié)點(diǎn)：4
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：4 Val：4
當(dāng)前隊(duì)列：[11,5,3,1,4,null,null,null,null,null,null]

17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：6 當(dāng)前隊(duì)列：[11,5,3,1,4,null,null,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：5 parent：2
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】替換過(guò)程，父子節(jié)點(diǎn)位置替換，繼續(xù)循環(huán)。父節(jié)點(diǎn)值：3 存放到位置：5
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：2 parent：0
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】值比對(duì)，父節(jié)點(diǎn)：11 目標(biāo)節(jié)點(diǎn)：6
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：2 Val：6
當(dāng)前隊(duì)列：[11,5,6,1,4,3,null,null,null,null,null]

17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：7 當(dāng)前隊(duì)列：[11,5,6,1,4,3,null,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：6 parent：2
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】替換過(guò)程，父子節(jié)點(diǎn)位置替換，繼續(xù)循環(huán)。父節(jié)點(diǎn)值：6 存放到位置：6
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：2 parent：0
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】值比對(duì)，父節(jié)點(diǎn)：11 目標(biāo)節(jié)點(diǎn)：7
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：2 Val：7
當(dāng)前隊(duì)列：[11,5,7,1,4,3,6,null,null,null,null]

17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：12 當(dāng)前隊(duì)列：[11,5,7,1,4,3,6,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：7 parent：3
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】替換過(guò)程，父子節(jié)點(diǎn)位置替換，繼續(xù)循環(huán)。父節(jié)點(diǎn)值：1 存放到位置：7
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：3 parent：1
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】替換過(guò)程，父子節(jié)點(diǎn)位置替換，繼續(xù)循環(huán)。父節(jié)點(diǎn)值：5 存放到位置：3
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：1 parent：0
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】替換過(guò)程，父子節(jié)點(diǎn)位置替換，繼續(xù)循環(huán)。父節(jié)點(diǎn)值：11 存放到位置：1
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：0 Val：12
當(dāng)前隊(duì)列：[12,11,7,5,4,3,6,1,null,null,null]

17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：15 當(dāng)前隊(duì)列：[12,11,7,5,4,3,6,1,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：8 parent：3
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】替換過(guò)程，父子節(jié)點(diǎn)位置替換，繼續(xù)循環(huán)。父節(jié)點(diǎn)值：5 存放到位置：8
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：3 parent：1
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】替換過(guò)程，父子節(jié)點(diǎn)位置替換，繼續(xù)循環(huán)。父節(jié)點(diǎn)值：11 存放到位置：3
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：1 parent：0
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】替換過(guò)程，父子節(jié)點(diǎn)位置替換，繼續(xù)循環(huán)。父節(jié)點(diǎn)值：12 存放到位置：1
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：0 Val：15
當(dāng)前隊(duì)列：[15,12,7,11,4,3,6,1,5,null,null]

17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：10 當(dāng)前隊(duì)列：[15,12,7,11,4,3,6,1,5,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：9 parent：4
17:23:45.083 [main] INFO queue.PriorityQueue – 【入隊(duì)】替換過(guò)程，父子節(jié)點(diǎn)位置替換，繼續(xù)循環(huán)。父節(jié)點(diǎn)值：4 存放到位置：9
17:23:45.083 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：4 parent：1
17:23:45.083 [main] INFO queue.PriorityQueue – 【入隊(duì)】值比對(duì)，父節(jié)點(diǎn)：12 目標(biāo)節(jié)點(diǎn)：10
17:23:45.083 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：4 Val：10
當(dāng)前隊(duì)列：[15,12,7,11,10,3,6,1,5,4,null]

17:23:45.083 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：9 當(dāng)前隊(duì)列：[15,12,7,11,10,3,6,1,5,4,null]
17:23:45.083 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：10 parent：4
17:23:45.083 [main] INFO queue.PriorityQueue – 【入隊(duì)】值比對(duì)，父節(jié)點(diǎn)：10 目標(biāo)節(jié)點(diǎn)：9
17:23:45.083 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：10 Val：9
當(dāng)前隊(duì)列：[15,12,7,11,10,3,6,1,5,4,9]

17:23:45.083 [main] INFO queue.PriorityQueue – 【入隊(duì)】元素：8 當(dāng)前隊(duì)列：[15,12,7,11,10,3,6,1,5,4,9,null,null,null,null,null,null,null,null,null,null,null,null,null]
17:23:45.083 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：11 parent：5
17:23:45.083 [main] INFO queue.PriorityQueue – 【入隊(duì)】替換過(guò)程，父子節(jié)點(diǎn)位置替換，繼續(xù)循環(huán)。父節(jié)點(diǎn)值：3 存放到位置：11
17:23:45.083 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：5 parent：2
17:23:45.083 [main] INFO queue.PriorityQueue – 【入隊(duì)】替換過(guò)程，父子節(jié)點(diǎn)位置替換，繼續(xù)循環(huán)。父節(jié)點(diǎn)值：7 存放到位置：5
17:23:45.083 [main] INFO queue.PriorityQueue – 【入隊(duì)】尋找當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)位置。k：2 parent：0
17:23:45.083 [main] INFO queue.PriorityQueue – 【入隊(duì)】值比對(duì)，父節(jié)點(diǎn)：15 目標(biāo)節(jié)點(diǎn)：8
17:23:45.083 [main] INFO queue.PriorityQueue – 【入隊(duì)】完成 Idx：2 Val：8
當(dāng)前隊(duì)列：[15,12,8,11,10,7,6,1,5,4,9,3,null,null,null,null,null,null,null,null,null,null,null,null]

17:23:45.083 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：15 下節(jié)點(diǎn)：12 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：12 下節(jié)點(diǎn)：11 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue – 【出隊(duì)】左右子節(jié)點(diǎn)比對(duì)，獲取最小值。left：1 right：5
17:23:45.083 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：11 下節(jié)點(diǎn)：5 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：8 Val：3
17:23:45.083 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：15
17:23:45.083 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：12 下節(jié)點(diǎn)：11 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue – 【出隊(duì)】左右子節(jié)點(diǎn)比對(duì)，獲取最小值。left：5 right：10
17:23:45.083 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：11 下節(jié)點(diǎn)：10 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：4 Val：9
17:23:45.083 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：12
17:23:45.083 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：11 下節(jié)點(diǎn)：10 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue – 【出隊(duì)】左右子節(jié)點(diǎn)比對(duì)，獲取最小值。left：5 right：9
17:23:45.083 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：10 下節(jié)點(diǎn)：9 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：4 Val：4
17:23:45.083 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：11
17:23:45.083 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：10 下節(jié)點(diǎn)：9 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：9 下節(jié)點(diǎn)：5 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：3 Val：3
17:23:45.084 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：10
17:23:45.084 [main] INFO queue.PriorityQueue – 【出隊(duì)】左右子節(jié)點(diǎn)比對(duì)，獲取最小值。left：5 right：8
17:23:45.084 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：9 下節(jié)點(diǎn)：8 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：8 下節(jié)點(diǎn)：7 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：5 Val：1
17:23:45.084 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：9
17:23:45.084 [main] INFO queue.PriorityQueue – 【出隊(duì)】左右子節(jié)點(diǎn)比對(duì)，獲取最小值。left：5 right：7
17:23:45.084 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：8 下節(jié)點(diǎn)：7 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：2 Val：6
17:23:45.084 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：8
17:23:45.084 [main] INFO queue.PriorityQueue – 【出隊(duì)】左右子節(jié)點(diǎn)比對(duì)，獲取最小值。left：5 right：6
17:23:45.084 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：7 下節(jié)點(diǎn)：6 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：2 Val：1
17:23:45.084 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：7
17:23:45.084 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：6 下節(jié)點(diǎn)：5 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：1 Val：4
17:23:45.084 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：6
17:23:45.084 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：5 下節(jié)點(diǎn)：4 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：1 Val：3
17:23:45.084 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：5
17:23:45.084 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換過(guò)程，節(jié)點(diǎn)的值比對(duì)。上節(jié)點(diǎn)：4 下節(jié)點(diǎn)：3 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：1 Val：1
17:23:45.084 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：4
17:23:45.084 [main] INFO queue.PriorityQueue – 【出隊(duì)】替換結(jié)果，最終更換位置。Idx：0 Val：1
17:23:45.084 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：3
17:23:45.084 [main] INFO heap.__test__.HeapTest – 測(cè)試結(jié)果：1

Process finished with exit code 0

大堆就是一個(gè)反序的輸出結(jié)果，從大到小的排序和輸出。

大堆空間：[15,12,8,11,10,7,6,1,5,4,9,3,null,null,null,null,null,null,null,null,null,null,null,null]

推薦學(xué)習(xí)：《java視頻教程》