摘要:滿二叉樹所有的節點都有個葉子節點,除了最后層葉子節點節點數和深度的關系第層上的節點數為第個節點的父節點左子節點右子節點參考下圖完全二叉樹有且僅有最底層葉子節點不完整就是完全二叉樹。例如把去掉最小堆父節點小于左右子節點的完全二叉樹。
按照下圖的配方,走了一遍源碼。
湊齊PriorityQueue就可以召喚神龍了。
Ler"s go go go!
/** * Priority queue represented as a balanced binary heap: the two * children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The * priority queue is ordered by comparator, or by the elements" * natural ordering, if comparator is null: For each node n in the * heap and each descendant d of n, n <= d. The element with the * lowest value is in queue[0], assuming the queue is nonempty. */ transient Object[] queue; // non-private to simplify nested class access
沒錯這是個數組,為了更好的理解注釋的含義,請看下面↓。
滿二叉樹:
所有的節點都有2個葉子節點,除了最后層葉子節點;
節點數n和深度d的關系 n=2^d-1;
第i層上的節點數為2^(i-1);
第n個節點的父節點:n/2,左子節點:2n,右子節點:2n+1;(參考下圖)
完全二叉樹:
有且僅有最底層葉子節點不完整就是完全二叉樹。(例如:把15去掉)
最小堆:
父節點小于左右子節點的完全二叉樹。
轉數組:
用數組來存儲二叉樹后(參見下圖)可得,根節點A[0];左子節點a[2n+1];右子節點a[2(n+1)],父節點a[(n-1)/2]。(n為數組下標,從0開始)
是的,優先隊列的存儲結構大概就是這樣推演而來。
heapify() --> siftDown() --> siftDownComparable() --> siftDownUsingComparator()/** * Establishes the heap invariant (described above) in the entire tree, * assuming nothing about the order of the elements prior to the call. */ @SuppressWarnings("unchecked") private void heapify() { for (int i = (size >>> 1) - 1; i >= 0; i--) siftDown(i, (E) queue[i]); } /** * Inserts item x at position k, maintaining heap invariant by * demoting x down the tree repeatedly until it is less than or * equal to its children or is a leaf. * * @param k the position to fill * @param x the item to insert */ private void siftDown(int k, E x) { if (comparator != null) siftDownUsingComparator(k, x); else siftDownComparable(k, x); } @SuppressWarnings("unchecked") private void siftDownComparable(int k, E x) { Comparable super E> key = (Comparable super E>)x; int half = size >>> 1; // loop while a non-leaf while (k < half) { int child = (k << 1) + 1; // assume left child is least Object c = queue[child]; int right = child + 1; if (right < size && ((Comparable super E>) c).compareTo((E) queue[right]) > 0) c = queue[child = right]; if (key.compareTo((E) c) <= 0) break; queue[k] = c; k = child; } queue[k] = key; } @SuppressWarnings("unchecked") private void siftDownUsingComparator(int k, E x) { int half = size >>> 1; while (k < half) { int child = (k << 1) + 1; //2n + 1,這里n是下標 Object c = queue[child]; int right = child + 1; if (right < size && comparator.compare((E) c, (E) queue[right]) > 0) // 找出最小子節點 c = queue[child = right]; if (comparator.compare(x, (E) c) <= 0) // 父節點小則退出循環,否則進行替換 break; queue[k] = c; k = child; } queue[k] = x; }
這是任意數組最小堆化的過程。如果是一個合格的最小堆,那么所有的父節點都在數組前半部分,而通過父節點又能得到左右子節點。因此源碼一上來就“size >>> 1”(相當于除以2),只需對前半部分進行循環處理,使得循環結束后所有父節點均大于左/右子節點。這里非根父節點會被多次比較到。heapify()后將得到上文所說的最小堆數組。
@SuppressWarnings("unchecked") public E poll() { if (size == 0) return null; int s = --size; modCount++; E result = (E) queue[0]; E x = (E) queue[s]; queue[s] = null; if (s != 0) siftDown(0, x); // ! return result; }
poll()的核心也是siftDown,而這里的“siftDown(0, x);”與之前的“siftDown(i, (E) queue[i]);”不同的是,下標0所對應的元素本非x。也就是說,這里進行了個轉換:把最后queue[s]替換了queue[0]進行新的最小堆數組化。
/** * Removes a single instance of the specified element from this queue, * if it is present. More formally, removes an element {@code e} such * that {@code o.equals(e)}, if this queue contains one or more such * elements. Returns {@code true} if and only if this queue contained * the specified element (or equivalently, if this queue changed as a * result of the call). * * @param o element to be removed from this queue, if present * @return {@code true} if this queue changed as a result of the call */ public boolean remove(Object o) { int i = indexOf(o); if (i == -1) return false; else { removeAt(i); return true; } } /** * Removes the ith element from queue. * * Normally this method leaves the elements at up to i-1, * inclusive, untouched. Under these circumstances, it returns * null. Occasionally, in order to maintain the heap invariant, * it must swap a later element of the list with one earlier than * i. Under these circumstances, this method returns the element * that was previously at the end of the list and is now at some * position before i. This fact is used by iterator.remove so as to * avoid missing traversing elements. */ @SuppressWarnings("unchecked") private E removeAt(int i) { // assert i >= 0 && i < size; modCount++; int s = --size; if (s == i) // removed last element queue[i] = null; else { E moved = (E) queue[s]; queue[s] = null; siftDown(i, moved); if (queue[i] == moved) { siftUp(i, moved); if (queue[i] != moved) return moved; } } return null; }
如你所見,remove()也用到了siftDown()(同時還有siftUp(),下面介紹)。這里 經過siftDown后,如果queue[i] == moved則表示queue[i]的左右子節點都大于moved,即保證了i節點子樹是最小堆,但queue[i]的父節點是否小于moved卻未知,故又進行了siftUp。(圖片來自【2】)
/** * Inserts item x at position k, maintaining heap invariant by * promoting x up the tree until it is greater than or equal to * its parent, or is the root. * * To simplify and speed up coercions and comparisons. the * Comparable and Comparator versions are separated into different * methods that are otherwise identical. (Similarly for siftDown.) * * @param k the position to fill * @param x the item to insert */ private void siftUp(int k, E x) { if (comparator != null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); } @SuppressWarnings("unchecked") private void siftUpComparable(int k, E x) { Comparable super E> key = (Comparable super E>) x; while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (key.compareTo((E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = key; } @SuppressWarnings("unchecked") private void siftUpUsingComparator(int k, E x) { while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (comparator.compare(x, (E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = x; }
與之相對的,還有名為siftUpComparable()/siftUpUsingComparator()的方法。在新增元素時被調用。新增元素放在下標為size的位置。這里的down與up指的是被比較對象x的去向。比較后x被賦值給子節點就是down,被賦值給父節點就是up。當然你來寫的時候也可能新增時,從上到下循環遍歷。
說點什么PriorityQueue有序;不允許為null;非線程安全;(PriorityBlockingQueue線程安全);沒有介紹的地方大抵與其他集合框架相似,如擴容機制等。
優先隊列每次出隊的元素都是優先級最高(權值最小)的元素,通過比較(Comparator或元素本身自然排序)決定優先級。
記得常來復習啊~~~
更多有意思的內容,歡迎訪問筆者小站: rebey.cn
推薦文章:【1】【深入理解Java集合框架】深入理解Java PriorityQueue;
【2】java集合——Queue;
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/67212.html
摘要:如今行至于此,當觀賞一方。由于所返回的無執行意義。源碼閱讀總體門檻相對而言比,畢竟大多數底層都由實現了。比心可通過這篇文章理解創建一個實例過程圖工作原理往期線路回顧源碼一帶一路系列之源碼一帶一路系列之源碼一帶一路系列之 本文以jdk1.8中LinkedHashMap.afterNodeAccess()方法為切入點,分析其中難理解、有價值的源碼片段(類似源碼查看是ctrl+鼠標左鍵的過程...
摘要:一路至此,風景過半。與雖然名字各異,源碼實現基本相同,除了增加了線程安全。同時注意溢出情況處理。同時增加了考慮并發問題。此外,源碼中出現了大量泛型如。允許為非線程安全有序。 一路至此,風景過半。ArrayList與Vector雖然名字各異,源碼實現基本相同,除了Vector增加了線程安全。所以作者建議我們在不需要線程安全的情況下盡量使用ArrayList。下面看看在ArrayList源...
摘要:同樣在源碼的與分別見看到老朋友和。這樣做可以降低性能消耗的同時,還可以減少序列化字節流的大小,從而減少網絡開銷框架中。使用了反射來尋找是否聲明了這兩個方法。十進制和,通過返回值能反應當前狀態。 Map篇暫告段落,卻并非離我們而去。這不在本篇中你就能經常見到她。HashSet、LinkedHashSet、TreeSet各自基于對應Map實現,各自源碼內容較少,因此歸納為一篇。 HashS...
摘要:本篇涉及少許以下簡稱新特性,請驢友們系好安全帶,準備開車。觀光線路圖是在中新增的一個方法,相對而言較為陌生。其作用是把的計算結果關聯到上即返回值作為新。實際上,乃縮寫,即二元函數之意類似。 本文以jdk1.8中HashMap.compute()方法為切入點,分析其中難理解、有價值的源碼片段(類似源碼查看是ctrl+鼠標左鍵的過程)。本篇涉及少許Java8(以下簡稱J8)新特性,請驢友們...
摘要:觀光線路圖將涉及到的源碼全局變量哈希表初始化長度默認值是負載因子默認表示的填滿程度。根據是否為零將原鏈表拆分成個鏈表,一部分仍保留在原鏈表中不需要移動,一部分移動到原索引的新鏈表中。 前言 本文以jdk1.8中HashMap.putAll()方法為切入點,分析其中難理解、有價值的源碼片段(類似ctrl+鼠標左鍵查看的源碼過程)。?觀光線路圖:putAll() --> putMapEnt...
閱讀 1626·2021-10-25 09:46
閱讀 3209·2021-10-08 10:04
閱讀 2354·2021-09-06 15:00
閱讀 2768·2021-08-19 10:57
閱讀 2077·2019-08-30 11:03
閱讀 970·2019-08-30 11:00
閱讀 2370·2019-08-26 17:10
閱讀 3545·2019-08-26 13:36