資訊專欄INFORMATION COLUMN
摘要：模型優先隊列是允許至少下列兩種操作的數據結構以及找出返回并刪除優先隊列中最小的元素。左式堆也是二叉樹，左式堆和二叉堆的唯一區別是左式堆不是理想平衡，而實際上趨向于非常不平衡。事實上，沿左式堆的右路徑是該堆中的最短路徑。
6.1 模型
優先隊列是允許至少下列兩種操作的數據結構：insert 以及 deleteMin（找出、返回并刪除優先隊列中最小的元素）。
insert 操作等價于 enqueue（入隊），而 deleteMin 則是運算 dequeue（出隊)在優先隊列中的等價操作。
一些簡單的實現可以使用簡單鏈表進行不排序的插入，則插入操作為 O(1)，但是刪除需要遍歷鏈表為 O(N)。
另一種方法是讓鏈表保持排序狀態：插入代價高昂 O(N)，但刪除為 O(1).但是 deleteMin 的操作比插入操作少，前者可能更好。
另外一種方法是使用二叉查找樹，它對這兩種操作的平均運行時間都為 O(log N)。
但是，由于我們刪除的唯一元素是最小元，反復出去左子樹的節點會損害樹的平衡使得右子樹加重，在最壞情況下 deleteMin 將左子樹刪空。
另外，使用查找樹有很多我們數據結構不需要的鏈。
二叉堆我們將要使用的數據結構叫做二叉堆（binary heap），它的使用對于優先隊列的實現相當普遍，以至于堆（heap）這個詞不加修飾的用在優先隊列的上下文中時，一般都是指數據結構的這種實現。
二叉堆有兩個性質：結構性和堆序性。
結構性質堆是一棵被完全填滿的二叉樹，有可能的例外是在底層，底層上的元素從左到右填入。這樣的樹被稱為完全二叉樹（complete binary tree）。
一棵高為 h 的完全二叉樹有 2h 到 2h+1 - 1 個節點。它的高度為 Log N，顯然它是 O(log N)。
因為二叉堆是滿二叉樹，所以在高度為 h-1 的樹包含
20 + ... + 2h-1 = 2h -1 個元素，
在高度為 h 的層上有 1 至 2h 個元素，所以應該有 2h 至 2h+1 - 1 個元素。
因為完全二叉樹這么有規律，所以它可以用一個數組表示而不需要使用鏈。
對于數組中任意位置 i 上的元素，其左兒子在位置 2i 上，右兒子在左兒子后的單元 (2i + 1)上。它的父親則在位置 [i / 2] 上。
堆序性質讓操作快速執行的性質是堆序性質（heap-order property）。由于我們想要快速找出最小元，因此最小的元應該在根上。如果我們考慮任意子樹也應該是一個堆，那么任意節點就給應該小于它的所有后裔。
基本的堆操作 insert（插入）為了將一個元素 X 插入到堆中，我們在下一個可用位置創建一個空穴，否則該堆將不是完全樹。如果 X 可以放在該空穴中而并不破壞對的序，那么插入完成。
否則，我們把空穴的父節點移入該空穴中，這樣空穴就朝著根的方向上冒一步。繼續該過程直到 X 能夠放入空穴中為止。
如下圖所示：為了插入 14，我們在堆的下一個可用位置上建立一個空穴，由于將 14 插入空穴破壞了堆序性質，因此將 31 移入該空穴。
在圖中，將元素從做到右執行插入，所以下一個空穴的位置應該在 31 的右節點上。
當刪除一個最小元是，要在根節點建立一個空穴。由于現在少了一個元素，因此堆中最后一個元素 X 必須移動帶該堆的某個地方。這是為了滿足二叉堆的結構性質 -- 它是一棵完全二叉樹，空穴只能在最后一層的最后一個元素之后
因此，我們將空穴的兩個兒子中較小者移入空穴這樣就把空穴向下推了一層。
重復該步驟直到 X 可以被放入空穴中。
例如，對于下面的例子中，我們先刪除元素 13，這將在二叉堆的根節點上建立一個空穴。隨后往里面插入數字 31.
在堆的實現中經常發生的錯誤是當堆中存在偶數個元素的時候，可能會遇到某個節點只有一個子節點的情況（只會在最下層出現）。
package com.mosby.ch06; /** * @author dhy */ public class BinaryHeap左式堆> { public BinaryHeap(){ this(DEFAULT_CAPACITY); } public BinaryHeap(int capacity){ currentSize = 0; array = new Comparable[capacity]; } /** * 向堆插入一個元素
* ** * 在這里我們的代碼使用了一個小技巧：我們現在的目的是要將當前堆中的空穴（初始為數組中最后一個元素之后） * 移動到一個滿足將 X 插入該空穴后不影響堆的性質的位置。* * @param x */ public void insert(T x){ //因為堆內部的數組實現的第一個元素是空 if(currentSize == array.length - 1){ enlargeArray(array.length * 2 + 1); } //當前空穴的位置在最后一個元素的后一位，同時插入空穴之后 currentSize 增加一。等同于下面的代碼 //int hole = currentSize + 1; //currentSize++; int hole = ++currentSize; for(; hole > 1 && x.compareTo((T) array[hole / 2]) < 0; hole /= 2){ array[hole] = array[hole / 2]; } array[hole] = x; } public T findMin(){ if(isEmpty()){ return null; } return (T) array[1]; } public T deleteMin(){ if(isEmpty()){ throw new RuntimeException("Under flow"); } T minItem = findMin(); array[1] = array[currentSize--]; percolateDown(1); return minItem; } public boolean isEmpty(){ return currentSize == 0; } public void makeEmpty(){ currentSize = 0; } private static final int DEFAULT_CAPACITY = 100; private int currentSize;//當前堆中元素個數 private Comparable[] array;//堆內部的以數組的形式存放 /** * 對空穴進行下濾 * @param hole */ private void percolateDown(int hole){ //這里 child 的初值不會影響程序的正確性，但是 eclipse 的編譯器有 bug， int child; 是無法通過編譯的 //在 IDEA 下可以直接 int child; int child = hole * 2; Comparable tmp = array[hole]; /** * 這里注意一點，hole * 2 <= currentSize，因為數組的第一個元素為空
* * 如果我們每次都將當前空穴的位置和它的父元素交換，那么對于一個元素上濾 d 層， * 那么由于交換而執行的賦值次數就是 3d。
* * 而這里，我們每次只是在滿足條件時將父節點的值賦給了這個空穴而沒有將空穴的值上濾。
* 這樣上濾 d 層將只需要 d 次對空穴的賦值和一次最后將 X 插入的賦值。總共 d+1 次賦值。 * *
* 數組中的實際元素應該是 array[i] - array[currentSize] */ for(; hole * 2 <= currentSize; hole = child){ child = hole * 2; /** * 在下濾的過程中，我們每次將當前節點的兩個子節點中較小的那個子節點跟空穴交換
* * 但是這必須要考慮一個問題，在最下層的時候，可能會有某個節點只有一個子節點
* * 而在非最下層則不會有這個問題，因為二叉堆是一個完全二叉樹。
* * 而根據二叉堆的插入性質（從左往右插入），那么只有一個元素的節點，這個元素的子節點肯定 * 就是二叉堆的最后一個節點。此時 hole == currentSize. */ if(child != currentSize && array[child + 1].compareTo((T) array[child]) < 0){ child++; } if(array[child].compareTo((T) tmp) < 0){ array[hole] = array[child]; }else{ break; } } array[hole] = tmp; } /** * 如果提供了通過數組初始化二叉堆的方式，那么在傳入一個數組后調用該方法即可得到一個二叉堆。 */ private void buildHeap(){ for(int i = currentSize / 2; i > 0; i--){ percolateDown(i); } } public void enlargeArray(int newSize){ Comparable[] newArray = new Comparable[newSize]; for(int i = 1; i <= currentSize; i++){ newArray[i] = array[i]; } array = newArray; } public int size(){ return currentSize; } }
設計一種堆結構像二叉堆那樣有效的支持合并操作（即以 O(N) 時間處理一個 merge）而且只使用一個數組似乎很困難。原因在于，合并似乎需要把一個數組拷貝到另外一個數組中去。
正因為如此，所有支持有效合并的高級數據結構都需要使用鏈式數據結構
左式堆 （leftist heap）像二叉堆一樣具有結構性和有序性。左式堆也是二叉樹，左式堆和二叉堆的唯一區別是：左式堆不是理想平衡（perfectly balanced），而實際上趨向于非常不平衡。
左式堆性質我們把任意節點 X 的零路徑長（null path length） npl(X) 定義為從 X 到一個不具有兩個兒子的節點的最短路徑長。因此，具有 0 個或一個兒子的節點的 npl 為 0，而 npl(null) = -1。
任意節點的零路徑長比它的所有兒子節點的零路徑長的最小值大1.這個結論也適用于少于兩個兒子的節點，因為 null 的零路徑長是 -1.
左式堆的性質是：對于堆中的每一個節點 X，左兒子的零路徑長大于等于右兒子的零路徑長。
實際上，對于左式堆的任意一個節點只能有三種情況，有兩個子節點、沒有子節點、僅有一個節點且該節點為左子節點。
也就是說，如果存在任意一個節點只有右節點，那么這個堆一定不是左式堆。但是，如果一個節點每個節點都滿足上面的條件，它不一定是左式堆，還需要滿足零路徑長的條件。
顯然，在上路中，左圖是一棵左式堆；而右圖則不是，因為右圖的根節點的左子節點的左子節點的零路徑長 == 0，而根節點的左子節點的右子節點的零路徑長 == 1.
這個性質使得它不是一棵理想平衡樹，因為它顯然偏重于使樹向左增加深度。
因為左式堆趨向于加深左路徑，所以右路徑應該短。事實上，沿左式堆的右路徑是該堆中的最短路徑。否則，就會存在某個節點 X 的左兒子的最短路徑長小于右兒子的最短路徑長。
node
/
node `node`
/ /
node node `null` node
例如，對于上面這個樹，對于標記的 node 節點是不符合左式堆的，因為它的左子節點的零路徑長是 -1，而右子節點的零路徑長是 0.
左式堆的基本操作左式堆的基本操作是合并。注意，插入只是合并的特殊性情況。
3 | 6 |
/ | / |
10 8 | 12 7 |
/ / | / / |
21 14 17 | 18 24 37 18 |
/ / | / |
23 26 | 33 |
合并具有大的 root 的堆與具有較小的 root 的堆的右節點
函數棧最上層
| 6 |
| / |
8 | 12 7 |
/ | / / |
17 | 18 24 37 18 |
/ | / |
26 | 33 |
函數棧的底層，該層等待上層函數的返回
3 |
/ |
10 |
/ |
21 14 |
/ |
23 |
遞歸的去進行 merge 操作
函數棧最上層
8 | 7 |
/ | / |
17 | 37 18 |
/ | |
26 | |
函數棧第二層
| 6 |
| / |
| 12 |
| / |
| 18 24 |
| / |
| 33 |
函數棧的底層，該層等待上層函數的返回
3 |
/ |
10 |
/ |
21 14 |
/ |
23 |
繼續進行遞歸 merge
函數棧最上層
8 | |
/ | |
17 | 18 |
/ | |
26 | |
函數棧第二層
| 7 |
| / |
| 37 |
| |
| |
函數棧第三層
| 6 |
| / |
| 12 |
| / |
| 18 24 |
| / |
| 33 |
函數棧的底層，該層等待上層函數的返回
3 |
/ |
10 |
/ |
21 14 |
/ |
23 |
繼續進行遞歸 merge
函數棧最上層，這個時候函數棧開始退出
null | 18 |
函數棧最二層
8 | |
/ | |
17 | |
/ | |
26 | |
函數棧第三層
| 7 |
| / |
| 37 |
| |
| |
函數棧第四層
| 6 |
| / |
| 12 |
| / |
| 18 24 |
| / |
| 33 |
函數棧的底層，該層等待上層函數的返回
3 |
/ |
10 |
/ |
21 14 |
/ |
23 |
函數棧開始退出
函數棧最上層，上層函數退出，同時必須更新 root 節點的 npl
8 | |
/ | |
17 18 | |
/ | |
26 | |
函數棧第二層
| 7 |
| / |
| 37 |
| |
| |
函數棧第三層
| 6 |
| / |
| 12 |
| / |
| 18 24 |
| / |
| 33 |
函數棧的底層，該層等待上層函數的返回
3 |
/ |
10 |
/ |
21 14 |
/ |
23 |
函數棧繼續退出，同時如果root左子樹的零路徑長小于右子樹的零路徑長則必須翻轉兩個子樹
函數棧最上層，上層函數退出，同時必須更新 root 節點的 npl
7
/
8 37 | |
/ | |
17 18 | |
/ | |
26 | |
函數棧第二層
| 6 |
| / |
| 12 |
| / |
| 18 24 |
| / |
| 33 |
函數棧的底層，該層等待上層函數的返回
3 |
/ |
10 |
/ |
21 14 |
/ |
23 |
最后得到的結果為 圖 6-24 所示。
遞歸的退出條件是：
被 merge 的兩個左式堆中任意一個為 null，則返回另一個；
兩個左式堆中那么具有較小 root 節點的左子節點為 null 時，將具有較大 root 的節點作為具有較小 root 的節點的左子節點，并返回具有較小 root 的幾點。這里隱含了一個信息：當一個左式堆的左子節點為 null 時，它的右子節點必定為 null。因為如果右子節點不為 null，那么它就不滿足左式堆的條件了。
如果這兩個堆中有一個為空，那么我們可以返回另外一個堆。
否則合并他們：
首先，我們遞歸的將具有大的 root 的堆與具有小的 root的堆的右子堆合并。我們在遞歸算法中需要保證遞歸得到的這棵樹是左式堆。
為什么這里是合并較大 root 的堆和較小 root 的堆的右子堆呢？
因為，我們合并出來的這個堆需要做為原來那個堆的右子堆，而根據左式堆的性質，一個節點所有的子節點都必須大于該節點。
圖 6-23 得到的不是左式堆。左式的性質在根處被破壞。
在我們步驟 1. 中得到的新的子樹是左式堆，而右子樹本身就是左式堆，所以這棵樹是不是滿足左式堆，只要左子樹的零路徑長大于新的右子樹的零路徑長即可。
如果不滿足，我們只需要將左子樹和右子樹的節點交換并更新零路徑長就可以了。
package com.mosby.ch06; /** * 左式堆：與普通二叉堆區別在于，左式堆不是一個完全二叉樹，并且左式堆不是一個理想平衡二叉樹。 */ public class LeftistHeap> { public LeftistHeap(){ root = null; } /** * 公有的 merge 方法將 anotherLeftistHeap 合并到控制堆中。 * 隨后 anotherLeftistHeap 變成了空的。 * 在第一趟，我們通過合并兩個堆的右路徑建立一棵新的樹。為此，以排序的方式安排 H1 和 H2 * 右路徑上的節點，保持他們各自的左兒子不變。 * 第二趟構成堆，兒子的交換工作在左式堆性質被破壞的那些節點上進行。 *
* @param anotherLeftistHeap 被合并的左式樹 */ public void merge(LeftistHeapanotherLeftistHeap){ if(this == null){ return ; } root = merge(root, this.root); anotherLeftistHeap.root = null; } /** * 向左式樹中插入新的元素 *
* @param x */ public void insert(E x){ root = merge(new Node<>(x), root); } /** * 尋找左式堆中最小的元素 *
* @return 左式堆最小元素 */ public E findMin(){ if(isEmpty()){ return null; } return root.theElement; } /** * 刪除左式堆中最小元素，并返回該元素 *
* @return 被刪除的元素 */ public E deleteMin(){ if(isEmpty()){ return null; } E minItem = root.theElement; root = merge(root.left, root.right); return minItem; } /** * 返回左式堆是否為空 *
* @return */ public boolean isEmpty(){ return root == null; } /** * 將左式堆設置為空堆 */ public void makeEmpty(){ root = null; } /** * 內部類用于表示左式堆的節點，相對于普通的二叉樹多了 npl（null path length）用于記錄空路徑長 *
* @param節點中的存儲的對象 */ private static class Node { Node(E theElement){ this(theElement, null, null); } Node(E theElement, Node left, Node right){ this.theElement = theElement; this.left = left; this.right = right; npl = 0; } E theElement; Node left; Node right; int npl; } private Node root; /** * merge 方法被用于消除一些特殊情形并保證 H1 有較小的根。 *
* @param h1 * @param h2 * @return */ private Nodemerge(Node h1, Node h2){ if(h1 == null){ return h2; } if(h2 == null){ return h1; } if(h1.theElement.compareTo(h2.theElement) < 0){ return merge1(h1, h2); }else{ return merge1(h2, h1); } } /** * merge1 執行實際的合并操作，并且在 merge1 的調用中，h1 小于 h2 *
* @param h1 * @param h2 * @return */ private Nodemerge1(Node h1, Node h2){ //根據左式堆的性質，如果 h1.left == null，那么 h1.right == null 也成立 if(h1.left == null){ h1.left = h2; }else{ h1.right = merge(h1.right, h2); if(h1.left.npl < h1.right.npl){ swapChildren(h1); } h1.npl = h1.right.npl + 1; } return h1; } private void swapChildren(Node t){ Node tmp = t.left; t.right = t.left; t.left = tmp; } }
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64801.html
摘要：二叉堆的有趣之處在于，其邏輯結構上像二叉樹，卻是用非嵌套的列表來實現。二叉堆結構性質為了更好地實現堆，我們采用二叉樹。圖完全二叉樹有意思的是我們用單個列表就能實現完全樹。下列所示的代碼是完全二叉堆的實現。 優先隊列的二叉堆實現 在前面的章節里我們學習了先進先出（FIFO）的數據結構：隊列（Queue）。隊列有一種變體叫做優先隊列（Priority Queue）。優先隊列的出隊（Dequ...
摘要：一個常見的例子就是優先隊列，還有排序算法之一的堆排序。另外我們還將學習堆排序，并將使用實現堆。堆排序在堆排序中，我們需要用給定的值構建一個一個堆。偽代碼如下從上面的偽代碼可以看到，堆排序的第一步就是構建一個堆。 堆是什么？ 堆是基于樹抽象數據類型的一種特殊的數據結構，用于許多算法和數據結構中。一個常見的例子就是優先隊列，還有排序算法之一的堆排序。這篇文章我們將討論堆的屬性、不同類型的堆...
摘要：二叉堆數據結構是一種特殊的二叉樹，他能高效快速的找出最大值和最小值，常應用于優先隊列和著名的堆排序算法中。 二叉堆數據結構是一種特殊的二叉樹，他能高效、快速的找出最大值和最小值，常應用于優先隊列和著名的堆排序算法中。 二叉堆 二叉堆有以下兩個特性： 是一顆完全二叉樹，表示數的每一層都有左側和右側子節點（除最后一層的葉節點），并且最后一層的葉節點盡可能是左側子節點 二叉堆不是最小堆就是...
摘要：選擇問題概述從個數當中選出第個最大者。基本的堆操作見數據結構與算法分析用優先隊列解決選擇問題算法將個元素讀入數組，對數組應用算法。參考文獻數據結構與算法分析語言描述尋找最小的個數 選擇問題（seletion problem）概述[1] 從N個數當中選出第k個最大者。 最簡單的兩種算法： 算法A1：排序-->返回k位置的數。時間復雜度O(N^2) 算法A2：先讀入前k個數-->排序...
閱讀 2431·2021-09-22 15:41
閱讀 1448·2021-08-19 10:54
閱讀 1755·2019-08-23 15:11
閱讀 3402·2019-08-23 10:23
閱讀 1428·2019-08-22 16:28
閱讀 799·2019-08-22 15:11
閱讀 739·2019-08-22 14:53
閱讀 710·2019-08-22 13:49
