堆與優先級隊列研究（C++）

 堆，是一個很有意思的資料結構。邏輯結構是樹，一般為二叉樹，每個節點的值都大于（小于）其子樹中的任意節點。也就是說，使用堆結構的數組中，元素 是部分有序的。而正是這個特點，使得在堆上，得到最大值（最小值）的時間複雜度為O(1)，移除最大值（最小值）、插入元素、改變元素值（或者是删除位置 已知的元素）的時間複雜度為O(lgn)。另外，用堆結構的排序是一種原地的、時間複雜度為O(nlgn)的排序算法。

在優先級隊列前先說一下堆排序。

堆排序和歸并排序都是時間複雜度為O(nlgn)的排序算法，不同的是，歸并排序不是原地排序，它需要額外的n的空間；而堆排序是在原數組中進行的。

堆排序的過程，首先需要在給定的數組上進行建堆，然後在此基礎上一個一個的取根節點放到數組的後部，從後向前排。

建堆的過程BuildHeap 代碼很簡單，從下到上對每個節點依次處理，進行中調用了另一個方法：Heapify ，這個才是核心（具體參見完整代碼中的私有BuildHeap(void) 方法與Heapify(ItemType items[], int index, int count, bool isMaxHeap) 方法）；Heapify 方法對指定節點的子樹進行堆化，具體地說，當除了根節點以外，其子樹中的所有節點都已經符合堆的要求時，Heapify 方 法會把指定的節點的子樹調整為一個堆，也就是把指定節點調整到子樹中合适的位置上，其時間複雜度為子樹的深度，O(lgn)。是以，可以算出建堆的時間複 雜度為O(n)，是線性的。這個時間複雜度怎麼得到的？n長度的樹，有lgn層，第h層（從0開始）至多有2^h的節點，進行一下求和就行了。

堆建好了，下來就是排序（具體可以見完整代碼中私有的SortTo(ItemType destitionArray[]) 方法）。因為堆的根節點是最值，是以隻需要依次把根節點和堆的最後一個元素交換位置，堆大小-1，再對根節點調用Heapify 就可以了。時間複雜度也就是n個Heapify ，O(nlgn)。

這樣進而得到總的排序時間複雜度O(nlgn)。

優先級隊列，目的是從隊列中取出的一個元素總是目前隊列中的最大值（最小值）。而堆剛好具有這個特點。當然，有序的ArrayList或者LinkedList也是可以的，但是慢，這個後面分析。

看一下優先級隊列都需要哪些操作。第一，其根本目的是能取出一個最值元素，這個就不用說了；第二，要能往隊列中插入元素。這是兩個核心的功能，另帶一些其他的輔助功能，如改變其中的某個元素的值，删除某個元素，得到其中的所有元素，得到其中元素個數等等。

給出優先級隊列的類的接口：

1. template   
2. <typename  ItemType>  
3. class  PriorityQueue {  
4.     PriorityQueue(bool  isMaxHeap =  true );  
5.     PriorityQueue(int  size,  bool  isMaxHeap =  true );  
6.     PriorityQueue(ItemType items[], int  count,  bool  isMaxHeap =  true );  
7.     int  Count( void );  
8.     ItemType Get();  
9.     ItemType Remove();  
10.     void  Insert(ItemType value);  
11.     void  Change( int  index, ItemType value);  
12.     ItemType Remove(int  index);  
13.     bool  ToArray(ItemType destinationArray[],  int  destinationSize);  
14.     ~PriorityQueue(void );  
15. } 

Remove() 方法是得到并移除第一個元素，Get() 僅僅是傳回第一個元素。這個優先級隊列用堆實作，進而可以得到主要方法Get() （O(1)）、Remove() （O(lgn)）、Insert() （O(lgn)）較好的性能。具體實作參見完整代碼。

Heapify 方法書上給的是個遞歸的，我給改成疊代的了，避免函數調用帶來的些許開銷，進而可以提高一點内隐的時間與空間的性能。

那麼為什麼用堆實作優先級隊列比較合适呢？有序的線性表呢？

這個不難想，對于線性表，基于數組實作：首先，如果無序，要Get() 、要Remove() ，肯定要找到個最值，如果每次都去重新搜尋，就很慢了，而且數組牽扯到資料的整體移動（O(n)）；而保持有序，雖然Get() 、Remove() 快，但是Insert(ItemType value) 費的功夫有些多，因為堆中隻是部分有序，而數組需要保持整體有序，又是資料整體移動（O(n)）。

基于連結清單的呢？連結清單的修改是很快，但連結清單如何快速搜尋與定位？建索引？-_-!

扯回來，說些關于具體實作時的問題。

當然，Change(int index, ItemType value) 與Remove(int index) 兩個方法在實際中是不實用的，或者是不現實的。因為通常情況下，不知道某個元素的index 是多少。通常要麼就不實作，要麼需要搜尋，或者有類似索引的機制。

還有，實際使用中隊列中存放的元素很可能是個什麼東西的指針，而不是一個沒什麼用的具體數值，這樣就還需要進行改進。

一種方式是原有的類不動，用一個實作了比較運算符的類或結構體的包裝類包裝一個有實際意義的東西，用這個類型當作PriorityQueue 的模闆參數。

或者是改造PriorityQueue ，把模闆參數ItemType 改成一個結構體或類，思想和上面的相似，不過這樣做功能會強大許多。比如添加一個這樣的内部類來替代模闆參數ItemType ：

1. class  QueueItem {  
2. public :  
3.     QueueItem(ItemType theValue, int  thePriority)  
4.             : priority(thePriority), value(theValue) {  
5.     }  
6.     // Getters and Setters   
7. private :  
8.     friend PriorityQueue;  
9.     inline void  SetOnwer(PriorityQueue* queue) {  
10.         onwer = queue;  
11.     }  
12.     inline void  SetIndex( int  index) {  
13.         this ->index = index;  
14.     }  
15.     inline int  GetIndex() {  
16.         return  index;  
17.     }  
18. private :  
19.     PriorityQueue* onwer;  
20.     int  index;  
21.     int  priority;  
22.     ItemType value;       
23. }; 

然後把原先代碼中，items 改為QueueItem 類型的數組；類内部的的ItemType 換成QueueItem 的指針。QueueItem 含有所在PriorityQueue 的index ，所有的地方注意改動這個；Insert 方法中new 一個QueueItem 來包裝ItemType ，并傳回此類的指針供外部更改使用（構造器就沒辦法了，可能無法保留帶有元素的構造方法）；移除的方法中注意回收QueueItem 的空間；涉及到index 的接口可以改為傳入QueueItem 的指針，PriorityQueue 可直接根據QueueItem 指針指向的對象得到index；…… 細節比較瑣碎，不再描述，這個已經超出了本文的範圍。

完整的類代碼如下：

1. #include <exception>   
2. #pragma once   
3. using  std::exception;  
4. template   
5. <typename  ItemType>  
6. class  PriorityQueue {  
7. private :  
8.     static   const   int  DefaultSize = 10;  
9. public :  
10.     PriorityQueue(bool  isMaxHeap =  true ) {  
11.         Initialize(nullptr, 0, DefaultSize, isMaxHeap);  
12.     }  
13.     PriorityQueue(int  size,  bool  isMaxHeap =  true ) {  
14.         Initialize(nullptr, 0, size, isMaxHeap);  
15.     }  
16.     PriorityQueue(ItemType items[], int  count,  bool  isMaxHeap =  true ) {  
17.         Initialize(items, count, count, isMaxHeap);  
18.     }  
19.     // Item count in queue.   
20.     inline   int  Count( void ) {  
21.         return  count;  
22.     }  
23.     // Only get first item.   
24.     inline  ItemType Get() {  
25.         if  (count == 0) {  
26.             // empty queue.   
27.             // do something here.   
28.             throw  exception();  
29.         } else  {  
30.             return  *items;  
31.         }  
32.     }  
33.     // Get and remove first item.   
34.     ItemType Remove() {  
35.         if  (count == 0) {  
36.             // empty queue.   
37.             // do something here.   
38.             throw  exception();  
39.         }  
40.         return  Remove(0);  
41.     }  
42.     // Add a new item into queue.   
43.     void  Insert(ItemType value) {  
44.         TryResize(true );  
45.         items[count - 1] = value;  
46.         TryMoveUp(count - 1, value);  
47.     }  
48.     // Change value at index.   
49.     void  Change( int  index, ItemType value) {  
50.         if  (index >= count) {  
51.             // out of range.   
52.             // throw exception or do nothing.   
53.             throw  exception();  
54.         }  
55.         if  (isMaxHeap ? value < items[index] : value > items[index]) {  
56.             TryMoveDown(index, value);  
57.         } else   if  (isMaxHeap ? value > items[index] : value < items[index]) {  
58.             TryMoveUp(index, value);  
59.         } else  {  
60.             // do nothing.   
61.         }  
62.     }  
63.     ItemType Remove(int  index) {  
64.         if  (index >= count) {  
65.             // out of range.   
66.             // throw exception or do nothing.   
67.             throw  exception();  
68.         }  
69.         ItemType result = items[index];  
70.         items[index] = items[count - 1];  
71.         TryResize(false );  
72.         if  (index != count - 1) {  
73.             Heapify(items, index, count, isMaxHeap);  
74.         }  
75.         return  result;  
76.     }  
77.     // Sort all items in queue to destinationArray, destinationSize for safe.   
78.     bool  ToArray(ItemType destinationArray[],  int  destinationSize) {  
79.         if  (destinationSize < count) {  
80.             // can not copy all items into destination array.   
81.             throw  exception();  
82.         }  
83.         SortTo(destinationArray);  
84.         return   true ;  
85.     }  
86.     ~PriorityQueue(void ) {  
87.         delete [] items;  
88.     }  
89. private :  
90.     void  Initialize(ItemType items[],  int  count,  int  size,  bool  isMaxHeap) {  
91.         if  (size < count) {  
92.             // throw exception or set a new size.   
93.             size = count + DefaultSize;  
94.         }  
95.         this ->maxSize = size;  
96.         this ->count = count;  
97.         this ->isMaxHeap = isMaxHeap;  
98.         this ->items =  new  ItemType[size];  
99.         if  (items != nullptr) {  
100.             for  ( int  i = 0; i < count; ++i) {  
101.                 this ->items[i] = items[i];  
102.             }  
103.             BuildHeap();  
104.         }  
105.     }  
106.     void  BuildHeap( void ) {  
107.         for  ( int  i = ParentIndex(count - 1); i >= 0; --i) {  
108.             Heapify(items, i, count, isMaxHeap);  
109.         }  
110.     }  
111.     // move items[index] down to the right position in its subtree.   
112.     void  Heapify(ItemType items[],  int  index,  int  count,  bool  isMaxHeap) {  
113.         int  currentIndex = index;  
114.         int  targetIndex = index;  
115.         if  (isMaxHeap) {  // ... how to do this better?   
116.             while  ( true ) {  
117.                 int  leftIndex = LeftChildIndex(currentIndex);  
118.                 int  rightIndex = RightChildIndex(currentIndex);  
119.                 if  (leftIndex < count && items[leftIndex] > items[targetIndex]) {  
120.                     targetIndex = leftIndex;  
121.                 }  
122.                 if  (rightIndex < count && items[rightIndex] > items[targetIndex]) {  
123.                     targetIndex = rightIndex;  
124.                 }  
125.                 if  (targetIndex != currentIndex) {  
126.                     Swap(items + targetIndex, items + currentIndex);  
127.                     currentIndex = targetIndex;  
128.                 } else  {  
129.                     break ;  
130.                 }  
131.             }  
132.         } else  {  
133.             while  ( true ) {  
134.                 int  leftIndex = LeftChildIndex(currentIndex);  
135.                 int  rightIndex = RightChildIndex(currentIndex);  
136.                 if  (leftIndex < count && items[leftIndex] < items[targetIndex]) {  
137.                     targetIndex = leftIndex;  
138.                 }  
139.                 if  (rightIndex < count && items[rightIndex] < items[targetIndex]) {  
140.                     targetIndex = rightIndex;  
141.                 }  
142.                 if  (targetIndex != currentIndex) {  
143.                     Swap(items + targetIndex, items + currentIndex);  
144.                     currentIndex = targetIndex;  
145.                 } else  {  
146.                     break ;  
147.                 }  
148.             }         
149.         }  
150.     }  
151.     inline   int  LeftChildIndex( int  parentIndex) {  
152.         return  RightChildIndex(parentIndex) - 1;  
153.     }  
154.     inline   int  RightChildIndex( int  parentIndex) {  
155.         return  ++parentIndex << 1;  
156.     }  
157.     inline   int  ParentIndex( int  index) {  
158.         return  (++index >> 1) - 1;  
159.     }  
160.     void  SortTo(ItemType destitionArray[]) {  
161.         // copy items.   
162.         for  ( int  i = 0; i < count; ++i) {  
163.             destitionArray[i] = items[i];  
164.         }  
165.         // only for exercises... do heap sort in destitionArray.   
166.         for  ( int  i = count, tempCount = count; i > 0; --i) {  
167.             Swap(destitionArray, destitionArray + tempCount - 1);  
168.             --tempCount;  
169.             Heapify(destitionArray, 0, tempCount, isMaxHeap);  
170.         }  
171.     }  
172.     void  Swap(ItemType* a, ItemType* b) {  
173.         ItemType temp = *a;  
174.         *a = *b;  
175.         *b = temp;  
176.     }  
177.     void  TryMoveUp( int  index, ItemType value) {  
178.         if  (isMaxHeap ? value < items[index] : value > items[index]) {  
179.             // do something about value error.   
180.             throw  exception();  
181.         }  
182.         items[index] = value;  
183.         int  currentIndex = index;  
184.         int  parentIndex = ParentIndex(index);  
185.         while  (index > 0 && (isMaxHeap ? items[parentIndex] < items[index] : items[parentIndex] > items[index])) {  
186.             Swap(items + index, items + parentIndex);  
187.             index = parentIndex;  
188.             parentIndex = ParentIndex(parentIndex);  
189.         }  
190.     }  
191.     void  TryMoveDown( int  index, ItemType value) {  
192.         if  (isMaxHeap ? value > items[index] : value < items[index]) {  
193.             // do something about value error.   
194.             throw  exception();  
195.         }  
196.         items[index] = value;  
197.         Heapify(items, index, count, isMaxHeap);  
198.     }  
199.     void  TryResize( bool  isIncrease) {  
200.         if  (isIncrease) {  
201.             if  (count >= maxSize) {  
202.                 maxSize = (maxSize << 1) + 10;  
203.                 NewItems(maxSize);  
204.             }  
205.             ++count;  
206.         } else  {  
207.             if  (count < maxSize >> 1) {  
208.                 maxSize = (maxSize >> 1) + 5;  
209.                 NewItems(maxSize);  
210.             }  
211.             --count;  
212.         }  
213.     }  
214.     void  NewItems( int  size) {  
215.         ItemType* newItems = new  ItemType[size];  
216.         // copy items.   
217.         for  ( int  i = 0; i < count; ++i) {  
218.             newItems[i] = items[i];  
219.         }  
220.         delete [] items;  
221.         items = newItems;  
222.     }  
223. private :  
224.     ItemType* items;  
225.     int  count;  
226.     int  maxSize;  
227.     bool  isMaxHeap;  
228. };