Java數(shù)據(jù)結(jié)構(gòu)之最小堆和最大堆的原理及實現(xiàn)詳解
一、前言
堆的歷史
堆的數(shù)據(jù)結(jié)構(gòu)有很多種體現(xiàn)形式，包括；2-3堆、B堆、斐波那契堆，而在 Java API 中最常用的是用于實現(xiàn)優(yōu)先隊列的二叉堆，它是由 JWJ Williams 在 1964 年引入的，作為堆排序算法的數(shù)據(jù)結(jié)構(gòu)。另外在 Dijkstra 算法等幾種高效的圖算法中，堆也是非常重要的。
二、堆的數(shù)據(jù)結(jié)構(gòu)
在計算機科學中，堆(heap) 的實現(xiàn)是一種基于樹的特殊的數(shù)據(jù)結(jié)構(gòu)，它可以在數(shù)組上構(gòu)建出樹的結(jié)構(gòu)體，并滿足堆的屬性；
最小堆：如果P? 是C? 的一個父級節(jié)點， 那么P? 的key(或value)應小于或等于C 的對應值。
最大堆：與最小堆的定義正好相反，最大堆(max heap) ,P? 的key(或value)大于C 的對應值。
三、堆的代碼實現(xiàn)
1. 實現(xiàn)介紹
堆的實現(xiàn)在 Java API 中主要體現(xiàn)在延遲隊列的實現(xiàn)二叉堆上，這里小傅哥單獨把這部分代碼拆分出來，了解下關于小堆和大堆的實現(xiàn)。
從對堆的數(shù)據(jù)結(jié)構(gòu)介紹上可以看到，小堆和大堆的唯一區(qū)別僅是對元素的排序方式不同。所以也就是說在存放和獲取元素的時候?qū)υ氐奶畛浜驼龝r，排序方式不同而已。
2. 入堆實現(xiàn)
堆的在存放元素時，以遵循它的特點，會在存放過程中，通過隊尾元素向上比對遷移。
private void siftUpComparable(int k, E x) {
logger.info("【入隊】元素：{} 當前隊列：{}", JSON.toJSONString(x), JSON.toJSONString(queue));
while (k > 0) {
// 獲取父節(jié)點Idx，相當于除以2
int parent = (k - 1) >>> 1;
logger.info("【入隊】尋找當前節(jié)點的父節(jié)點位置。k：{} parent：{}", k, parent);
Object e = queue[parent];
// 如果當前位置元素，大于父節(jié)點元素，則退出循環(huán)
if (compareTo(x, (E) e) >= 0) {
logger.info("【入隊】值比對，父節(jié)點：{} 目標節(jié)點：{}", JSON.toJSONString(e), JSON.toJSONString(x));
break;
}
// 相反父節(jié)點位置大于當前位置元素，則進行替換
logger.info("【入隊】替換過程，父子節(jié)點位置替換，繼續(xù)循環(huán)。父節(jié)點值：{} 存放到位置：{}", JSON.toJSONString(e), k);
queue[k] = e;
k = parent;
}
queue[k] = x;
logger.info("【入隊】完成 Idx：{} Val：{} \r\n當前隊列：{} \r\n", k, JSON.toJSONString(x), JSON.toJSONString(queue));
}入堆的實現(xiàn) add 方法最終會調(diào)用到 siftUpComparable 方法，進行排序的方式進行處理。而這個排序 compareTo 方法是由具體的 MinHeap、MaxHeap 來做實現(xiàn)。
以入堆元素2舉例，如圖所示入堆過程。
首先將元素2掛到隊列尾部，之后通過 (k - 1) >>> 1 計算父節(jié)點位置，與對應元素進行比對和判斷交換。
交換過程包括 2->6、2->5，以此交換結(jié)束后元素保存完畢。
3. 出堆實現(xiàn)
元素的出堆其實很簡單，只要把根元素直接刪除彈出即可。但剩余接下里的步驟才是復雜的，因為需要在根元素遷移走后，尋找另外的最小元素遷移到對頭。這個過程與入堆正好相反，這是一個不斷向下遷移的過程。
private void siftDownComparable(int k, E x) {
// 先找出中間件節(jié)點
int half = size >>> 1;
while (k < half) {
// 找到左子節(jié)點和右子節(jié)點，兩個節(jié)點進行比較，找出最大的值
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
// 左子節(jié)點與右子節(jié)點比較，取最小的節(jié)點
if (right < size && compareTo((E) c, (E) queue[right]) > 0) {
logger.info("【出隊】左右子節(jié)點比對，獲取最小值。left：{} right：{}", JSON.toJSONString(c), JSON.toJSONString(queue[right]));
c = queue[child = right];
}
// 目標值與c比較，當目標值小于c值，退出循環(huán)。說明此時目標值所在位置適合，遷移完成。
if (compareTo(x, (E) c) <= 0) {
break;
}
// 目標值小于c值，位置替換，繼續(xù)比較
logger.info("【出隊】替換過程，節(jié)點的值比對。上節(jié)點：{} 下節(jié)點：{} 位置替換", JSON.toJSONString(queue[k]), JSON.toJSONString(c));
queue[k] = c;
k = child;
}
// 把目標值放到對應位置
logger.info("【出隊】替換結(jié)果，最終更換位置。Idx：{} Val：{}", k, JSON.toJSONString(x));
queue[k] = x;
}不斷地向下遷移元素。這個過程會比對左右子節(jié)點的值，找到最小的。所以整個過程會比入堆麻煩一些。
這里以彈出元素1舉例，之后將堆尾元素替換到相應的位置。整個過程分為6張圖表述。
- 圖1到圖2，找出根元素彈出。
- 圖3到圖4，將根元素向下遷移，與子元素比對，并替換位置。如果這個位置與8相比，小于8則繼續(xù)向下遷移。
- 圖4到圖5，繼續(xù)遷移，在原節(jié)點4的位置對應的兩個子元素，都比8大，這個時候就可以停下來了。
- 圖5到圖6，更換元素位置，把隊尾的元素替換到對應元素1向下遷移檢測的位置。
4. 小堆實現(xiàn)
小堆是一個正序比對
public class MinHeap extends Heap<Integer> {
@Override
public int compareTo(Integer firstElement, Integer secondElement) {
return firstElement.compareTo(secondElement);
}
}測試
@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("測試結(jié)果：{}", heap.poll());
}
}結(jié)果
17:21:30.053 [main] INFO queue.PriorityQueue - 【入隊】元素：3 當前隊列：[1,null,null,null,null,null,null,null,null,null,null]
17:21:30.055 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：1 parent：0
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節(jié)點：1 目標節(jié)點：3
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：1 Val：3
當前隊列：[1,3,null,null,null,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】元素：5 當前隊列：[1,3,null,null,null,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：2 parent：0
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節(jié)點：1 目標節(jié)點：5
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：2 Val：5
當前隊列：[1,3,5,null,null,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】元素：11 當前隊列：[1,3,5,null,null,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：3 parent：1
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節(jié)點：3 目標節(jié)點：11
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：3 Val：11
當前隊列：[1,3,5,11,null,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】元素：4 當前隊列：[1,3,5,11,null,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：4 parent：1
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節(jié)點：3 目標節(jié)點：4
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：4 Val：4
當前隊列：[1,3,5,11,4,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】元素：6 當前隊列：[1,3,5,11,4,null,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：5 parent：2
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節(jié)點：5 目標節(jié)點：6
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：5 Val：6
當前隊列：[1,3,5,11,4,6,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】元素：7 當前隊列：[1,3,5,11,4,6,null,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：6 parent：2
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節(jié)點：5 目標節(jié)點：7
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：6 Val：7
當前隊列：[1,3,5,11,4,6,7,null,null,null,null] 17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】元素：12 當前隊列：[1,3,5,11,4,6,7,null,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：7 parent：3
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節(jié)點：11 目標節(jié)點：12
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：7 Val：12
當前隊列：[1,3,5,11,4,6,7,12,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】元素：15 當前隊列：[1,3,5,11,4,6,7,12,null,null,null]
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：8 parent：3
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節(jié)點：11 目標節(jié)點：15
17:21:30.057 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：8 Val：15
當前隊列：[1,3,5,11,4,6,7,12,15,null,null]
17:21:30.057 [main] INFO queue.PriorityQueue - 【入隊】元素：10 當前隊列：[1,3,5,11,4,6,7,12,15,null,null]
17:21:30.057 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：9 parent：4
17:21:30.057 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節(jié)點：4 目標節(jié)點：10
17:21:30.057 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：9 Val：10
當前隊列：[1,3,5,11,4,6,7,12,15,10,null]
17:21:30.057 [main] INFO queue.PriorityQueue - 【入隊】元素：9 當前隊列：[1,3,5,11,4,6,7,12,15,10,null]
17:21:30.057 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：10 parent：4
17:21:30.057 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節(jié)點：4 目標節(jié)點：9
17:21:30.057 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：10 Val：9
當前隊列：[1,3,5,11,4,6,7,12,15,10,9]
17:21:30.057 [main] INFO queue.PriorityQueue - 【入隊】元素：8 當前隊列：[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 - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：11 parent：5
17:21:30.057 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節(jié)點：6 目標節(jié)點：8
17:21:30.057 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：11 Val：8
當前隊列：[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 - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：1 下節(jié)點：3 位置替換
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】左右子節(jié)點比對，獲取最小值。left：11 right：4
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：3 下節(jié)點：4 位置替換
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】左右子節(jié)點比對，獲取最小值。left：10 right：9
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：4 Val：8
17:21:30.057 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：1
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：3 下節(jié)點：4 位置替換
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】左右子節(jié)點比對，獲取最小值。left：11 right：8
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：4 下節(jié)點：8 位置替換
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：4 Val：9
17:21:30.057 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：3
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】左右子節(jié)點比對，獲取最小值。left：8 right：5
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：4 下節(jié)點：5 位置替換
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：5 下節(jié)點：6 位置替換
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：5 Val：10
17:21:30.057 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：4
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】左右子節(jié)點比對，獲取最小值。left：8 right：6
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：5 下節(jié)點：6 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】左右子節(jié)點比對，獲取最小值。left：10 right：7
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：6 下節(jié)點：7 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：6 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：5
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】左右子節(jié)點比對，獲取最小值。left：8 right：7
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：6 下節(jié)點：7 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：7 下節(jié)點：10 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：5 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：6
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：7 下節(jié)點：8 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】左右子節(jié)點比對，獲取最小值。left：11 right：9
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：8 下節(jié)點：9 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：4 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：7
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：8 下節(jié)點：9 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：9 下節(jié)點：11 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：3 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：8
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】左右子節(jié)點比對，獲取最小值。left：11 right：10
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：9 下節(jié)點：10 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：2 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：9
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：10 下節(jié)點：11 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：1 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：10
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：11 下節(jié)點：12 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：1 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：11
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：0 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：15
Process finished with exit code 0
小堆就是一個正序的輸出結(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]
- 小堆就是一個正序的輸出結(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. 大堆實現(xiàn)
小堆是一個反序比對
public class MaxHeap extends Heap<Integer> {
@Override
public int compareTo(Integer firstElement, Integer secondElement) {
return secondElement.compareTo(firstElement);
}
}測試
@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("測試結(jié)果：{}", heap.poll());
}
}結(jié)果
17:23:45.079 [main] INFO queue.PriorityQueue - 【入隊】元素：3 當前隊列：[1,null,null,null,null,null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：1 parent：0
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節(jié)點位置替換，繼續(xù)循環(huán)。父節(jié)點值：1 存放到位置：1
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：0 Val：3
當前隊列：[3,1,null,null,null,null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】元素：5 當前隊列：[3,1,null,null,null,null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：2 parent：0
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節(jié)點位置替換，繼續(xù)循環(huán)。父節(jié)點值：3 存放到位置：2
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：0 Val：5
當前隊列：[5,1,3,null,null,null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】元素：11 當前隊列：[5,1,3,null,null,null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：3 parent：1
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節(jié)點位置替換，繼續(xù)循環(huán)。父節(jié)點值：1 存放到位置：3
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：1 parent：0
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節(jié)點位置替換，繼續(xù)循環(huán)。父節(jié)點值：5 存放到位置：1
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：0 Val：11
當前隊列：[11,5,3,1,null,null,null,null,null,null,null]
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】元素：4 當前隊列：[11,5,3,1,null,null,null,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：4 parent：1
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節(jié)點：5 目標節(jié)點：4
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：4 Val：4
當前隊列：[11,5,3,1,4,null,null,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】元素：6 當前隊列：[11,5,3,1,4,null,null,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：5 parent：2
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節(jié)點位置替換，繼續(xù)循環(huán)。父節(jié)點值：3 存放到位置：5
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：2 parent：0
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節(jié)點：11 目標節(jié)點：6
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：2 Val：6
當前隊列：[11,5,6,1,4,3,null,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】元素：7 當前隊列：[11,5,6,1,4,3,null,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：6 parent：2
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節(jié)點位置替換，繼續(xù)循環(huán)。父節(jié)點值：6 存放到位置：6
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：2 parent：0
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節(jié)點：11 目標節(jié)點：7
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：2 Val：7
當前隊列：[11,5,7,1,4,3,6,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】元素：12 當前隊列：[11,5,7,1,4,3,6,null,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：7 parent：3
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節(jié)點位置替換，繼續(xù)循環(huán)。父節(jié)點值：1 存放到位置：7
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：3 parent：1
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節(jié)點位置替換，繼續(xù)循環(huán)。父節(jié)點值：5 存放到位置：3
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：1 parent：0
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節(jié)點位置替換，繼續(xù)循環(huán)。父節(jié)點值：11 存放到位置：1
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：0 Val：12
當前隊列：[12,11,7,5,4,3,6,1,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】元素：15 當前隊列：[12,11,7,5,4,3,6,1,null,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：8 parent：3
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節(jié)點位置替換，繼續(xù)循環(huán)。父節(jié)點值：5 存放到位置：8
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：3 parent：1
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節(jié)點位置替換，繼續(xù)循環(huán)。父節(jié)點值：11 存放到位置：3
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：1 parent：0
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節(jié)點位置替換，繼續(xù)循環(huán)。父節(jié)點值：12 存放到位置：1
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：0 Val：15
當前隊列：[15,12,7,11,4,3,6,1,5,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】元素：10 當前隊列：[15,12,7,11,4,3,6,1,5,null,null]
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：9 parent：4
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節(jié)點位置替換，繼續(xù)循環(huán)。父節(jié)點值：4 存放到位置：9
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：4 parent：1
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節(jié)點：12 目標節(jié)點：10
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：4 Val：10
當前隊列：[15,12,7,11,10,3,6,1,5,4,null]
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】元素：9 當前隊列：[15,12,7,11,10,3,6,1,5,4,null]
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：10 parent：4
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節(jié)點：10 目標節(jié)點：9
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：10 Val：9
當前隊列：[15,12,7,11,10,3,6,1,5,4,9]
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】元素：8 當前隊列：[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 - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：11 parent：5
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節(jié)點位置替換，繼續(xù)循環(huán)。父節(jié)點值：3 存放到位置：11
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：5 parent：2
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節(jié)點位置替換，繼續(xù)循環(huán)。父節(jié)點值：7 存放到位置：5
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】尋找當前節(jié)點的父節(jié)點位置。k：2 parent：0
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節(jié)點：15 目標節(jié)點：8
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】完成 Idx：2 Val：8
當前隊列：[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 - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：15 下節(jié)點：12 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：12 下節(jié)點：11 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】左右子節(jié)點比對，獲取最小值。left：1 right：5
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：11 下節(jié)點：5 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：8 Val：3
17:23:45.083 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：15
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：12 下節(jié)點：11 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】左右子節(jié)點比對，獲取最小值。left：5 right：10
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：11 下節(jié)點：10 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：4 Val：9
17:23:45.083 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：12
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：11 下節(jié)點：10 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】左右子節(jié)點比對，獲取最小值。left：5 right：9
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：10 下節(jié)點：9 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：4 Val：4
17:23:45.083 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：11
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：10 下節(jié)點：9 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：9 下節(jié)點：5 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：3 Val：3
17:23:45.084 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：10
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】左右子節(jié)點比對，獲取最小值。left：5 right：8
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：9 下節(jié)點：8 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：8 下節(jié)點：7 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：5 Val：1
17:23:45.084 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：9
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】左右子節(jié)點比對，獲取最小值。left：5 right：7
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：8 下節(jié)點：7 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：2 Val：6
17:23:45.084 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：8
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】左右子節(jié)點比對，獲取最小值。left：5 right：6
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：7 下節(jié)點：6 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：2 Val：1
17:23:45.084 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：7
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：6 下節(jié)點：5 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：1 Val：4
17:23:45.084 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：6
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：5 下節(jié)點：4 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：1 Val：3
17:23:45.084 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：5
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節(jié)點的值比對。上節(jié)點：4 下節(jié)點：3 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：1 Val：1
17:23:45.084 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：4
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換結(jié)果，最終更換位置。Idx：0 Val：1
17:23:45.084 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：3
17:23:45.084 [main] INFO heap.__test__.HeapTest - 測試結(jié)果：1
Process finished with exit code 0
大堆就是一個反序的輸出結(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]
以上就是Java數(shù)據(jù)結(jié)構(gòu)之最小堆和最大堆的原理及實現(xiàn)詳解的詳細內(nèi)容，更多關于Java數(shù)據(jù)結(jié)構(gòu) 堆的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要為大家詳細介紹了Java簡易計算器程序設計的相關參考資料，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2015-10-10
Java程序生成exe可執(zhí)行文件詳細教程(圖文說明)
這篇文章主要介紹了Java程序生成exe可執(zhí)行文件詳細教程，有需要的朋友可以參考一下2013-12-12
ApiOperation和ApiParam注解依賴的安裝和使用以及注意事項說明
這篇文章主要介紹了ApiOperation和ApiParam注解依賴的安裝和使用以及注意事項說明,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-09-09
日常工作中?Map?絕對是我們?Java?程序員高頻使用的一種數(shù)據(jù)結(jié)構(gòu)，那?Map?都有哪些遍歷方式呢？這篇文章就帶大家看一下，看看你經(jīng)常使用的是哪一種2022-11-11
springboot通過SchedulingConfigurer實現(xiàn)多定時任務注冊及動態(tài)修改執(zhí)行周期(示例詳解)
這篇文章主要介紹了springboot通過SchedulingConfigurer實現(xiàn)多定時任務注冊及動態(tài)修改執(zhí)行周期,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-06-06
JAVA如何把數(shù)據(jù)庫的數(shù)據(jù)處理成樹形結(jié)構(gòu)
本文介紹了JAVA如何把數(shù)據(jù)庫的數(shù)據(jù)處理成樹形結(jié)構(gòu)，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-09-09
java實現(xiàn)二分法查找出數(shù)組重復數(shù)字
這篇文章主要為大家詳細介紹了java實現(xiàn)二分法查找出數(shù)組重復數(shù)字，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-11-11
java實現(xiàn)解析二進制文件的方法(字符串、圖片)
本篇文章主要介紹了java實現(xiàn)解析二進制文件的方法(字符串、圖片)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-02-02
這篇文章主要介紹了使用maven自定義插件開發(fā)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-06-06
SpringBoot使用AOP實現(xiàn)統(tǒng)計全局接口訪問次數(shù)詳解
這篇文章主要介紹了SpringBoot通過AOP實現(xiàn)對全局接口訪問次數(shù)的統(tǒng)計，文章從相關問題展開全文內(nèi)容詳情，具有一定的參考價值，需要的小伙伴可以參考一下2022-06-06