您好,登錄后才能下訂單哦!
這篇文章主要介紹“Java數(shù)據(jù)結(jié)構(gòu)之最小堆和最大堆怎么實現(xiàn)”,在日常操作中,相信很多人在Java數(shù)據(jù)結(jié)構(gòu)之最小堆和最大堆怎么實現(xiàn)問題上存在疑惑,小編查閱了各式資料,整理出簡單好用的操作方法,希望對大家解答”Java數(shù)據(jù)結(jié)構(gòu)之最小堆和最大堆怎么實現(xiàn)”的疑惑有所幫助!接下來,請跟著小編一起來學(xué)習(xí)吧!
堆的歷史
堆的數(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 算法等幾種高效的圖算法中,堆也是非常重要的。
在計算機科學(xué)中,堆(heap) 的實現(xiàn)是一種基于樹的特殊的數(shù)據(jù)結(jié)構(gòu),它可以在數(shù)組上構(gòu)建出樹的結(jié)構(gòu)體,并滿足堆的屬性;
最小堆:如果P 是C 的一個父級節(jié)點, 那么P 的key(或value)應(yīng)小于或等于C 的對應(yīng)值。
最大堆:與最小堆的定義正好相反,最大堆(max heap) ,P 的key(或value)大于C 的對應(yīng)值。
堆的實現(xiàn)在 Java API 中主要體現(xiàn)在延遲隊列的實現(xiàn)二叉堆上,這里小傅哥單獨把這部分代碼拆分出來,了解下關(guān)于小堆和大堆的實現(xiàn)。
從對堆的數(shù)據(jù)結(jié)構(gòu)介紹上可以看到,小堆和大堆的唯一區(qū)別僅是對元素的排序方式不同。所以也就是說在存放和獲取元素的時候?qū)υ氐奶畛浜驼龝r,排序方式不同而已。
堆的在存放元素時,以遵循它的特點,會在存放過程中,通過隊尾元素向上比對遷移。
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é)點位置,與對應(yīng)元素進行比對和判斷交換。
交換過程包括 2->6、2->5,以此交換結(jié)束后元素保存完畢。
元素的出堆其實很簡單,只要把根元素直接刪除彈出即可。但剩余接下里的步驟才是復(fù)雜的,因為需要在根元素遷移走后,尋找另外的最小元素遷移到對頭。這個過程與入堆正好相反,這是一個不斷向下遷移的過程。
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; } // 把目標值放到對應(yīng)位置 logger.info("【出隊】替換結(jié)果,最終更換位置。Idx:{} Val:{}", k, JSON.toJSONString(x)); queue[k] = x; }
不斷地向下遷移元素。這個過程會比對左右子節(jié)點的值,找到最小的。所以整個過程會比入堆麻煩一些。
這里以彈出元素1舉例,之后將堆尾元素替換到相應(yīng)的位置。整個過程分為6張圖表述。
圖1到圖2,找出根元素彈出。
圖3到圖4,將根元素向下遷移,與子元素比對,并替換位置。如果這個位置與8相比,小于8則繼續(xù)向下遷移。
圖4到圖5,繼續(xù)遷移,在原節(jié)點4的位置對應(yīng)的兩個子元素,都比8大,這個時候就可以停下來了。
圖5到圖6,更換元素位置,把隊尾的元素替換到對應(yīng)元素1向下遷移檢測的位置。
小堆是一個正序比對
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]
小堆是一個反序比對
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]
到此,關(guān)于“Java數(shù)據(jù)結(jié)構(gòu)之最小堆和最大堆怎么實現(xiàn)”的學(xué)習(xí)就結(jié)束了,希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí),快去試試吧!若想繼續(xù)學(xué)習(xí)更多相關(guān)知識,請繼續(xù)關(guān)注億速云網(wǎng)站,小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。