首頁 > 文章 > Java > Java資料結構之最小堆與最大堆的原理及實作詳解

Java資料結構之最小堆與最大堆的原理及實作詳解

WBOY轉載: 2022-09-05 17:30:292444瀏覽

本篇文章為大家帶來了關於java的相關知識，在電腦科學中，堆(heap) 的實作是一種基於樹的特殊的資料結構，它可以在陣列上建構出樹的結構體，並滿足堆的屬性，以下就來聊聊Java資料結構中的堆，感興趣的可以了解一下。

一、前言

堆的歷史

堆的資料結構有很多種體現形式，包括；2-3堆、B堆、斐波那契堆，而在Java API 中最常用的是用於實現優先隊列的二叉堆，它是由JWJ Williams 在1964 年引入的，作為堆排序演算法的資料結構。另外在 Dijkstra 演算法等幾種高效率的圖演算法中，堆也是非常重要的。

二、堆的資料結構

在電腦科學中，堆(heap) 的實作是一種基於樹的特殊的資料結構，它可以在陣列上建構出樹的結構體，並滿足堆的屬性；

最小堆：如果P 是C 的一個父級節點，那麼P 的key(或value)應小於或等於C 的對應值。

最大堆：與最小堆的定義剛好相反，最大堆(max heap) ,P 的key(或value)大於C 的對應值。

三、堆的程式碼實作

1. 實作介紹

堆的實作在Java API 中主要體現在延遲佇列的實作二元堆上，這裡小傅哥單獨把這部分程式碼拆分出來，了解下關於小堆和大堆的實作。

從對堆的資料結構介紹可以看到，小堆和大堆的唯一差異僅是對元素的排序方式不同。所以也就是說在存放和取得元素的時候對元素的填充和摘除時，排序方式不同而已。

2. 入堆實現

堆的在存放元素時，以遵循它的特點，會在存放過程中，透過隊尾元素向上比對遷移。

private void siftUpComparable(int k, E x) {
    logger.info("【入队】元素：{} 当前队列：{}", JSON.toJSONString(x), JSON.toJSONString(queue));
    while (k > 0) {
        // 获取父节点Idx，相当于除以2
        int parent = (k - 1) >>> 1;
        logger.info("【入队】寻找当前节点的父节点位置。k：{} parent：{}", k, parent);
        Object e = queue[parent];
        // 如果当前位置元素，大于父节点元素，则退出循环
        if (compareTo(x, (E) e) >= 0) {
            logger.info("【入队】值比对，父节点：{} 目标节点：{}", JSON.toJSONString(e), JSON.toJSONString(x));
            break;
        }
        // 相反父节点位置大于当前位置元素，则进行替换
        logger.info("【入队】替换过程，父子节点位置替换，继续循环。父节点值：{} 存放到位置：{}", 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));
}

入堆的實作 add 方法最終會呼叫到 siftUpComparable 方法，進行排序的方式進行處理。而這個排序 compareTo 方法是由具體的 MinHeap、MaxHeap 來做實作。

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

先將元素2掛到佇列尾部，之後透過(k - 1) >>> 1 計算父節點位置，與對應元素進行比對和判斷交換。

交換過程包括 2->6、2->5，以此交換結束後元素保存完畢。

3. 出堆實作

元素的出堆其實很簡單，只要把根元素直接刪除彈出即可。但剩餘接下裡的步驟才是複雜的，因為需要在根元素遷移走後，尋找另外的最小元素遷移到對頭。這個過程與入堆正好相反，這是一個不斷向下遷移的過程。

private void siftDownComparable(int k, E x) {
    // 先找出中间件节点
    int half = size >>> 1;
    while (k < half) {
        // 找到左子节点和右子节点，两个节点进行比较，找出最大的值
        int child = (k << 1) + 1;
        Object c = queue[child];
        int right = child + 1;
        // 左子节点与右子节点比较，取最小的节点
        if (right < size && compareTo((E) c, (E) queue[right]) > 0) {
            logger.info("【出队】左右子节点比对，获取最小值。left：{} right：{}", JSON.toJSONString(c), JSON.toJSONString(queue[right]));
            c = queue[child = right];
        }
        // 目标值与c比较，当目标值小于c值，退出循环。说明此时目标值所在位置适合，迁移完成。
        if (compareTo(x, (E) c) <= 0) {
            break;
        }
        // 目标值小于c值，位置替换，继续比较
        logger.info("【出队】替换过程，节点的值比对。上节点：{} 下节点：{} 位置替换", JSON.toJSONString(queue[k]), JSON.toJSONString(c));
        queue[k] = c;
        k = child;
    }
    // 把目标值放到对应位置
    logger.info("【出队】替换结果，最终更换位置。Idx：{} Val：{}", k, JSON.toJSONString(x));
    queue[k] = x;
}

不斷向下遷移元素。這個過程會比對左右子節點的值，找到最小的。所以整個過程會比入堆更麻煩。

這裡以彈出元素1舉例，之後將堆尾元素替換到對應的位置。整個過程分為6張圖表述。

圖1到圖2，找出根元素彈出。
圖3到圖4，將根元素向下遷移，與子元素比對，並替換位置。如果這個位置與8相比，小於8則繼續向下遷移。
圖4到圖5，繼續遷移，在原節點4的位置對應的兩個子元素，都比8大，這個時候就可以停下來了。
圖5到圖6，更換元素位置，把隊尾的元素替換到對應元素1向下遷移偵測的位置。

4. 小堆實作

小堆是正序比對

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("测试结果：{}", heap.poll());
    }
}

結果

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 - 【入隊】尋找目前節點的父節點位置。 k：1 parent：0
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節點：1 目標節點：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 - 【入隊】尋找目前節點的父節點位置。 k：2 parent：0
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節點：1 目標節點：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 - 【入隊】尋找目前節點的父節點位置。 k：3 parent：1
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節點：3 目標節點：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 - 【入隊】尋找目前節點的父節點位置。 k：4 parent：1
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節點：3 目標節點：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 - 【入隊】尋找目前節點的父節點位置。 k：5 parent：2
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節點：5 目標節點：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 - 【入隊】尋找目前節點的父節點位置。 k：6 parent：2
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節點：5 目標節點：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 - 【入隊】尋找目前節點的父節點位置。 k：7 parent：3
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節點：11 目標節點：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 - 【入隊】尋找目前節點的父節點位置。 k：8 parent：3
17:21:30.056 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節點：11 目標節點：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 - 【入隊】尋找目前節點的父節點位置。 k：9 parent：4
17:21:30.057 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節點：4 目標節點：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 - 【入隊】尋找目前節點的父節點位置。 k：10 parent：4
17:21:30.057 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節點：4 目標節點：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 - 【入隊】尋找目前節點的父節點位置。 k：11 parent：5
17:21:30.057 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節點：6 目標節點：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 - 【出隊】替換過程，節點的值比對。上節點：1 下節點：3 位置替換
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】左右子節點比對，取得最小值。 left：11 right：4
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：3 下節點：4 位置替換
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】左右子節點比對，取得最小值。 left：10 right：9
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】替換結果，最終更換位置。 Idx：4 Val：8
17:21:30.057 [main] INFO heap.__test__.HeapTest - 測試結果：1
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：3 下節點：4 位置替換
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】左右子節點比對，取得最小值。 left：11 right：8
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：4 下節點：8 位置替換
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】替換結果，最終更換位置。 Idx：4 Val：9
17:21:30.057 [main] INFO heap.__test__.HeapTest - 測試結果：3
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】左右子節點比對，取得最小值。 left：8 right：5
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：4 下節點：5 位置替換
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：5 下節點：6 位置替換
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】替換結果，最終更換位置。 Idx：5 Val：10
17:21:30.057 [main] INFO heap.__test__.HeapTest - 測試結果：4
17:21:30.057 [main] INFO queue.PriorityQueue - 【出隊】左右子節點比對，取得最小值。 left：8 right：6
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：5 下節點：6 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】左右子節點比對，取得最小值。 left：10 right：7
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：6 下節點：7 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換結果，最終更換位置。 Idx：6 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 測試結果：5
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】左右子節點比對，取得最小值。 left：8 right：7
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：6 下節點：7 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：7 下節點：10 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換結果，最終更換位置。 Idx：5 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 測試結果：6
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：7 下節點：8 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】左右子節點比對，取得最小值。 left：11 right：9
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：8 下節點：9 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換結果，最終更換位置。 Idx：4 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 測試結果：7
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：8 下節點：9 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：9 下節點：11 位置替換
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：3 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：8
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】左右子节点比对，获取最小值。left：11 right：10
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：9 下节点：10 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：2 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：9
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：10 下节点：11 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：1 Val：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：10
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换过程，节点的值比对。上节点：11 下节点：12 位置替换
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：1 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：11
17:21:30.058 [main] INFO queue.PriorityQueue - 【出队】替换结果，最终更换位置。Idx：0 Val：15
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：12
17:21:30.058 [main] INFO heap.__test__.HeapTest - 测试结果：15

Process finished with exit code 0
小堆就是一个正序的输出结果，从小到大的排序和输出。
小堆空间：[1,3,5,11,4,6,7,12,15,10,9,8,null,null,null,null,null,null,null,null,null,null,null,null]

小堆就是一个正序的输出结果，从小到大的排序和输出。
小堆空间：[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. 大堆实现

小堆是一个反序比对

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("测试结果：{}", heap.poll());
    }
}

结果

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 - 【入隊】尋找目前節點的父節點位置。 k：1 parent：0
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節點位置替換，繼續循環。父節點值：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 - 【入隊】尋找目前節點的父節點位置。 k：2 parent：0
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節點位置替換，繼續循環。父節點值：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 - 【入隊】尋找目前節點的父節點位置。 k：3 parent：1
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節點位置替換，繼續循環。父節點值：1 存放到位置：3
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】尋找目前節點的父節點位置。 k：1 parent：0
17:23:45.081 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節點位置替換，繼續循環。父節點值：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 - 【入隊】尋找目前節點的父節點位置。 k：4 parent：1
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節點：5 目標節點：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 - 【入隊】尋找目前節點的父節點位置。 k：5 parent：2
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節點位置替換，繼續循環。父節點值：3 存放到位置：5
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】尋找目前節點的父節點位置。 k：2 parent：0
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節點：11 目標節點：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 - 【入隊】尋找目前節點的父節點位置。 k：6 parent：2
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節點位置替換，繼續循環。父節點值：6 存放到位置：6
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】尋找目前節點的父節點位置。 k：2 parent：0
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節點：11 目標節點：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 - 【入隊】尋找目前節點的父節點位置。 k：7 parent：3
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節點位置替換，繼續循環。父節點值：1 存放到位置：7
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】尋找目前節點的父節點位置。 k：3 parent：1
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節點位置替換，繼續循環。父節點值：5 存放到位置：3
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】尋找目前節點的父節點位置。 k：1 parent：0
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節點位置替換，繼續循環。父節點值：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 - 【入隊】尋找目前節點的父節點位置。 k：8 parent：3
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節點位置替換，繼續循環。父節點值：5 存放到位置：8
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】尋找目前節點的父節點位置。 k：3 parent：1
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節點位置替換，繼續循環。父節點值：11 存放到位置：3
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】尋找目前節點的父節點位置。 k：1 parent：0
17:23:45.082 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節點位置替換，繼續循環。父節點值：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 - 【入隊】尋找目前節點的父節點位置。 k：9 parent：4
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節點位置替換，繼續循環。父節點值：4 存放到位置：9
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】尋找目前節點的父節點位置。 k：4 parent：1
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節點：12 目標節點：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 - 【入隊】尋找目前節點的父節點位置。 k：10 parent：4
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節點：10 目標節點：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 - 【入隊】尋找目前節點的父節點位置。 k：11 parent：5
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節點位置替換，繼續循環。父節點值：3 存放到位置：11
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】尋找目前節點的父節點位置。 k：5 parent：2
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】替換過程，父子節點位置替換，繼續循環。父節點值：7 存放到位置：5
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】尋找目前節點的父節點位置。 k：2 parent：0
17:23:45.083 [main] INFO queue.PriorityQueue - 【入隊】值比對，父節點：15 目標節點：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 - 【出隊】替換過程，節點的值比對。上節點：15 下節點：12 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：12 下節點：11 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】左右子節點比對，取得最小值。 left：1 right：5
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：11 下節點：5 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換結果，最終更換位置。 Idx：8 Val：3
17:23:45.083 [main] INFO heap.__test__.HeapTest - 測試結果：15
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：12 下節點：11 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】左右子節點比對，取得最小值。 left：5 right：10
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：11 下節點：10 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換結果，最終更換位置。 Idx：4 Val：9
17:23:45.083 [main] INFO heap.__test__.HeapTest - 測試結果：12
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：11 下節點：10 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】左右子節點比對，取得最小值。 left：5 right：9
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：10 下節點：9 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換結果，最終更換位置。 Idx：4 Val：4
17:23:45.083 [main] INFO heap.__test__.HeapTest - 測試結果：11
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：10 下節點：9 位置替換
17:23:45.083 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：9 下節點：5 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換結果，最終更換位置。 Idx：3 Val：3
17:23:45.084 [main] INFO heap.__test__.HeapTest - 測試結果：10
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】左右子節點比對，取得最小值。 left：5 right：8
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：9 下節點：8 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：8 下節點：7 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換結果，最終更換位置。 Idx：5 Val：1
17:23:45.084 [main] INFO heap.__test__.HeapTest - 測試結果：9
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】左右子節點比對，取得最小值。 left：5 right：7
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：8 下節點：7 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換結果，最終更換位置。 Idx：2 Val：6
17:23:45.084 [main] INFO heap.__test__.HeapTest - 測試結果：8
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】左右子節點比對，取得最小值。 left：5 right：6
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：7 下節點：6 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換結果，最終更換位置。 Idx：2 Val：1
17:23:45.084 [main] INFO heap.__test__.HeapTest - 測試結果：7
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：6 下節點：5 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換結果，最終更換位置。 Idx：1 Val：4
17:23:45.084 [main] INFO heap.__test__.HeapTest - 測試結果：6
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：5 下節點：4 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換結果，最終更換位置。 Idx：1 Val：3
17:23:45.084 [main] INFO heap.__test__.HeapTest - 測試結果：5
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換過程，節點的值比對。上節點：4 下節點：3 位置替換
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換結果，最終更換位置。 Idx：1 Val：1
17:23:45.084 [main] INFO heap.__test__.HeapTest - 測試結果：4
17:23:45.084 [main] INFO queue.PriorityQueue - 【出隊】替換結果，最終更換位置。 Idx：0 Val：1
17:23:45.084 [main] INFO heap.__test__.HeapTest - 測試結果：3
17:23:45.084 [main] INFO heap.__test__.HeapTest - 測試結果：1

Process finished with exit code 0

大堆就是一個反序的輸出結果，從大到小的排序和輸出。

大堆空間：[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影片教學》

以上是Java資料結構之最小堆與最大堆的原理及實作詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！

陳述：

本文轉載於：jb51.net。如有侵權，請聯絡admin@php.cn刪除

上一篇：Java Web動態網站開發教學課程下一篇：Java Web動態網站開發教學課程

看更多