二叉堆 - gaochundong－IT工程師數位筆記本

文章出處

在計算機科學中，堆（Heap）是一種基于樹（Tree）的特殊的數據結構。堆需要滿足堆特性（Heap Property）：如果節點 A 是節點 B 的父節點，則節點 A 中的鍵值與節點 B 中的鍵值的比較順序關系將適用于堆中的所有節點。也就是可以總結為兩種情況。

父節點的鍵值大于等于子節點的鍵值 A(Parent(i)) ≥ A[i] ，則根節點的鍵值為堆中的最大值。這種類型的堆叫做最大堆（Max Heap）。
父節點的鍵值小于等于子節點的鍵值 A(Parent(i)) ≤ A[i]，則根節點的鍵值為堆中的最小值。這種類型的堆叫做最小堆（Min Heap）。

由于堆中的最大值或最小值總是被存儲在根節點（Root Node）中，所以名字稱為堆。堆不是一種排序的數據結構，可認為是部分排序的結構。從堆的圖形結構來看，在相同層級中的節點間沒有任何特定的關系，即使是兄弟節點。

堆經常被應用于優先隊列（Priority Queue），當你需要找到隊列中最高優先級或者最低優先級的元素時，使用堆結構可以幫助你快速的定位元素。

堆實現與基本操作

常見的堆實現為二叉堆（Binary Heap），其實際上是一顆二叉樹（Binary Tree），并且是一顆完全二叉樹（Complete Binary Tree）。如下圖中展示了一個完全二叉的最大堆。

當堆被實現為完全二叉樹時，其高度為最小高度。如果堆中有 n 個節點，則最小高度為 Θ(lg n)。

實現堆結構時通常使用數組結構（Array），并且元素間不需要指針引用。使用完全二叉樹或者滿二叉樹實現堆時可以保持最優的空間效率。通常第一個元素或最后一個元素將保存根節點，根節點后緊跟著其兩個子節點，兩個子節點后將緊跟著 4 個這兩個子節點的子節點，以此類推。因此，在一個以 0 為起點的數組中，位置 i 處的節點的子節點的位置將位于 2i+1 和 2i+2 處。平衡一個堆的操作將使用元素互換的方式，所以對堆進行排序無需使用額外的空間，堆排序（heapsort）即是用了這種就地排序（In-Place）的方式。

堆排序

堆排序（Heap Sort）是指利用堆這種數據結構所設計的一種排序算法。二叉堆數據結構是一種數組對象，它可以被視為一棵完全二叉樹。樹中每個節點與數組中存放該節點值的那個元素對應。在堆排序算法中，我們使用最大堆。

堆節點的訪問

通常堆是通過一維數組來實現的。在數組起始為 0 的情形中，如果 i 為當前節點的索引，則有

父節點在位置 floor((i-1)/2)；
左子節點在位置 (2*i+1)；
右子節點在位置 (2*i+2)；

堆的操作

在堆的數據結構中，堆中的最大值總是位于根節點。堆中定義以下幾種操作：

最大堆調整（Max-Heapify）：將堆的末端子節點作調整，使得子節點永遠小于父節點，保持最大堆性質的關鍵。運行時間為 O(lg n)。
創建最大堆（Build-Max-Heap）：在無序的輸入數組基礎上構造出最大堆。運行時間為 O(n)。
堆排序（HeapSort）：對一個數組進行原地排序，卸載位在第一個數據的根節點，并做最大堆調整的遞歸運算。運行時間為 O(n*lg n)。
抽取最大值（Extract-Max）：相當于執行一次最大堆調整，最大值在根處。運行時間為 O(lg n)。

算法復雜度

最差時間復雜度 O(n*logn)
平均時間復雜度 Θ(n*logn)
最優時間復雜度 O(n*logn)
最差空間復雜度 O(n)，輔助空間 O(1)

示例代碼

  1   class Program
  2   {
  3     static void Main(string[] args)
  4     {
  5       int[] unsorted = { 4, 9, 5, 2, 6, 3, 7, 1, 8 };
  6 
  7       HeapSortByMaxHeap(unsorted);
  8 
  9       foreach (var key in unsorted)
 10       {
 11         Console.Write("{0} ", key);
 12       }
 13 
 14       Console.Read();
 15     }
 16 
 17     static void HeapSortByMaxHeap(int[] unsorted)
 18     {
 19       // build the heap in array so that largest value is at the root
 20       BuildMaxHeap(unsorted);
 21 
 22       // swap root node and the last heap node
 23       for (int i = unsorted.Length - 1; i >= 1; i--)
 24       {
 25         // array[0] is the root and largest value. 
 26         // the swap moves it in front of the sorted elements
 27         int max = unsorted[0];
 28         unsorted[0] = unsorted[i];
 29         unsorted[i] = max; // now, the largest one is at the end
 30 
 31         // the swap ruined the heap property, so restore it
 32         // the heap size is reduced by one
 33         MaxHeapify(unsorted, 0, i - 1);
 34       }
 35     }
 36 
 37     static void BuildMaxHeap(int[] unsorted)
 38     {
 39       // put elements of array in heap order, in-place
 40       // start is assigned the index in array of the last parent node
 41       // the last element in 0-based array is at index count-1; 
 42       // find the parent of that element
 43       for (int i = (unsorted.Length / 2) - 1; i >= 0; i--)
 44       {
 45         // move a node down in the tree, as long as needed
 46         // shift down the node at index start to the proper place 
 47         // such that all nodes below the start index are in heap order
 48         MaxHeapify(unsorted, i, unsorted.Length - 1);
 49       }
 50       // after shifting down the root all nodes/elements are in heap order
 51     }
 52 
 53     static void MaxHeapify(int[] unsorted, int root, int bottom)
 54     {
 55       int rootValue = unsorted[root];
 56       int left = root * 2 + 1; // start from left child
 57 
 58       // while the root has at least one child
 59       while (left <= bottom)
 60       {
 61         // has more children
 62         if (left < bottom)
 63         {
 64           // if there is a right child and that child is greater
 65           if (unsorted[left] < unsorted[left + 1])
 66           {
 67             left = left + 1;
 68           }
 69         }
 70 
 71         // compare root and the older children
 72         if (rootValue < unsorted[left])
 73         {
 74           // swap
 75           unsorted[root] = unsorted[left];
 76           root = left;
 77 
 78           // repeat to continue sifting down the child now
 79           left = root * 2 + 1; // continue from left child
 80         }
 81         else
 82         {
 83           left = bottom + 1;
 84         }
 85       }
 86 
 87       unsorted[root] = rootValue;
 88     }
 89 
 90     static void HeapSortByMinHeap(int[] unsorted)
 91     {
 92       BuildMinHeap(unsorted);
 93 
 94       for (int i = unsorted.Length - 1; i >= 1; i--)
 95       {
 96         int min = unsorted[0];
 97         unsorted[0] = unsorted[i];
 98         unsorted[i] = min;
 99 
100         MinHeapify(unsorted, 0, i - 1);
101       }
102 
103       // reverse
104       for (int i = 0; i < (unsorted.Length / 2); i++)
105       {
106         int t = unsorted[i];
107         unsorted[i] = unsorted[unsorted.Length - 1 - i];
108         unsorted[unsorted.Length - 1 - i] = t;
109       }
110     }
111 
112     static void BuildMinHeap(int[] unsorted)
113     {
114       for (int i = (unsorted.Length / 2) - 1; i >= 0; i--)
115       {
116         MinHeapify(unsorted, i, unsorted.Length - 1);
117       }
118     }
119 
120     static void MinHeapify(int[] unsorted, int root, int bottom)
121     {
122       int rootValue = unsorted[root];
123       int left = root * 2 + 1; // start from left child
124 
125       // while the root has at least one child
126       while (left <= bottom)
127       {
128         // has more children
129         if (left < bottom)
130         {
131           // if there is a right child and that child is smaller
132           if (unsorted[left] > unsorted[left + 1])
133           {
134             left = left + 1;
135           }
136         }
137 
138         // compare root and the older children
139         if (rootValue > unsorted[left])
140         {
141           // swap
142           unsorted[root] = unsorted[left];
143           root = left;
144 
145           // repeat to continue sifting down the child now
146           left = root * 2 + 1; // continue from left child
147         }
148         else
149         {
150           left = bottom + 1;
151         }
152       }
153 
154       unsorted[root] = rootValue;
155     }
156   }