有幾種明顯的方法實現優先隊列： 1.使用簡單鏈表在表頭以O(1)執行插入操作，遍歷該鏈表需要O(N)。另一方法是始終保持表有序，插入操作代價為O(N)，deleteMin花費為O(1)。 2.使用二叉查找樹。插入、刪除操作平均時間均為O(logN)。實現優先隊列要刪除最小元素，那么將會不斷在左子樹中刪除，會損害樹的平衡，會使右子樹加重。這樣，在最壞情況下，左子樹為空，則樹相當于鏈表，這樣其操作的時間界限就會變為最壞情況。另外，查找樹實現有些過分，因為它支持大量并不需要的操作。 二叉堆是實現優先隊列的常見方法。它是完全二叉樹，有規律可循，因此可用數組實現而不使用鏈表。如果從數組的下標為1的位置開始存元素（下標0處不存），那么數組中某位置i上的元素，其左孩子在位置2i，右孩子在2i+1位置上。 要快速找到最小值，則使用小根堆，根元素最小。 由于二叉堆是完全二叉樹，因此其高度為不大于logN的最大整數。插入操作、刪除操作的最壞時間為O(logN)，平均時間為O(logN)。 以下代碼以vector容器為基本數組實現小根堆，使用泛型編程實現： 這里用到了泛型編程，對于泛型編程有注意的地方，參考《[泛型編程注意不能將模板類的成員函數放在獨立的實現文件中](http://blog.csdn.net/u013074465/article/details/42030093)》。 刪除堆的過程就是要下濾的。 而堆排序用到了刪除堆的操作，因此，堆排序也是要下濾的。 對任意輸入序列建立堆也要下濾，因為該過程就是一系列元素排序的過程。 ~~~ //6heap.h #ifndef TEST_HEAP_H #define TEST_HEAP_H #include "test.h" /* 這里建立的是小根堆，元素存在vector容器中，根從下標為1的元素開始 */ template <typename T> class BinaryHeap { public: ?explicit BinaryHeap(int capacity = 100) ??? ?:array(capacity + 1), current_size(0) {} ?explicit BinaryHeap(const vector<T>& items) ??? ?:array(items.size() + 10), current_size(items.size()) { ??? ?int i; ??? ?for (i = 0; i < items.size(); i++) ??? ??? ?array[i + 1] = items[i]; ??? ?BuildHeap(); ?} ?bool IsEmpty() const { ??? ?return current_size == 0; ?} ?const T& FindMin() const { ??? ?if (IsEmpty()) ??? ??? ?cout << "No items in binary heap" << endl; ??? ?return array[1]; ?} ?/* ?堆的插入操作是“上濾”的過程。最壞時間為O(logN)，平均時間為O(logN)。 ?先在堆的下一個空閑位置上建立一個空穴，如果這樣不破壞堆的性質，那么插入完成。 ?否則，將空穴父節點的元素移入空穴，這樣空穴上升了一層，到達父節點的位置。 ?繼續該過程，直到插入值可以放入空穴為止。 ?*/ ?void Insert(const T& value)?? ?{ ??? ?if (current_size == array.size() - 1) //空間不夠，重分配 ??? ??? ?array.resize(array.size() * 2); ??? ?int hole = ++current_size; //在堆的下一個空閑位置建立一個空穴 ??? ?/* ??? ?在空穴沒上濾到根部并且插入值小于空穴父節點時， ??? ?將父節點移入空穴，空穴位置上升一層 ??? ?*/ ??? ?for ( ; hole > 1 && value < array[hole / 2]; hole /= 2) ??? ??? ?array[hole] = array[hole / 2]; ??? ?array[hole] = value; //將值插入到合適位置 ?? } ?/* ?刪除操作最壞時間為O(logN)，平均時間為O(logN)。 ?刪除最小值時，根成空穴，且堆要少一個元素， ?因此原堆的最后一個元素X將要放到堆的某個位置； ?如果X可以放到空穴中則完成；否則要將空穴的兒子中較小的元素放入空穴，空穴 ?下移，重復該過程直到X可以放入空穴。 ?*/ ?void DeleteMin() { ??? ?if (IsEmpty()) ??? ??? ?cout << "No items in binary heap" << endl; ??? ?array[1] = array[current_size--]; ??? ?PercolateDown(1); ?} ?void DeleteMin(T& min_item) { ??? ?if (IsEmpty()) ??? ??? ?cout << "No items in binary heap" << endl; ??? ?min_item = array[1]; ??? ?array[1] = array[current_size--]; ??? ?PercolateDown(1); ?} ?void MakeEmpty() { ??? ?current_size = 0; ?} ?void PrintItems() { ??? ?cout << "Items: "; ??? ?int i = 1; ??? ?while (i <= current_size) { ??? ??? ?cout << array[i++] << " "; ??? ?} ??? ?cout << endl; ?} private: ?int current_size; ?vector<T> array; ?/* ?建立堆的操作最壞時間為O(NlogN)，平均時間為O(N) ?建立堆的過程就是堆排序的過程 ?*/ ?void BuildHeap() { ??? ?int i; ??? ?for (i = current_size / 2; i > 0; i--) ??? ??? ?PercolateDown(i); ?} ?/* ?該函數完成“下濾”過程。 ?刪除堆的過程就是要下濾的。 ?而堆排序用到了刪除堆的操作，因此，堆排序也是要下濾的。 ?對任意輸入序列建立堆也要下濾。 ?該函數的做法是將插入值置入沿著從根開始 ?包含最小兒子的一條路徑上的正確位置 ?*/ ?void PercolateDown(int hole) { ??? ?int pos_child; ??? ?T tmp = array[hole]; ??? ?//當空穴位置沒有到達堆的尾部前，循環向下層找空穴位置 ??? ?for ( ; hole * 2 <= current_size; hole = pos_child) { ??? ??? ?pos_child = 2 * hole; ??? ??? ?/* ??? ??? ?下邊語句是要將較小孩子的下標移入空穴，將空穴移入下一層。 ??? ??? ?下邊的pos_child != current_size條件是控制當堆的節點為偶數時情況， ??? ??? ?當堆節點為偶數時，最后一個非葉節點只有一個左孩子，則此時要找的 ??? ??? ?較小孩子的下標就是左孩子的下標，即不用執行下邊第一個if ??? ??? ?*/ ??? ??? ?if (pos_child != current_size && array[pos_child + 1] < array[pos_child]) ??? ??? ??? ?pos_child++; ??? ??? ?if (array[pos_child] < tmp)? //如果較小孩子比父節點小，則空穴下移一層 ??? ??? ??? ?array[hole] = array[pos_child]; ??? ??? ?else ??? ??? ??? ?break; ??? ?} ??? ?array[hole] = tmp; ?} }; #endif ~~~ ~~~ //test.cpp #include "6heap.h" int main() { ?BinaryHeap<int> heap; ?heap.Insert(22); ?heap.Insert(12); ?heap.Insert(7); ?heap.Insert(1); ?heap.PrintItems(); ?vector<double> dvec; ?int i; ?for (i = 10; i > 0; --i) ??? ?dvec.push_back(i); ?BinaryHeap<double> dheap(dvec); ?dheap.PrintItems(); ?heap.DeleteMin(); ?heap.PrintItems(); ?dheap.DeleteMin(); ?dheap.DeleteMin(); ?dheap.PrintItems(); ?return 0; } ~~~