最小堆實現代碼

參考算法導論、數據結構相關書籍，寫得最小堆實現的源代碼如下：

  1 //
  2 //--最小堆實例
  3 //
  4 
  5 #include <iostream>
  6 #include <vector>
  7 #include <string>
  8 using namespace std;
  9 
 10 template<typename Comparable>
 11 class minHeap
 12 {
 13 public:
 14     explicit minHeap(int capacity = 0);//顯示構造函數，只能用于對象的構造而不能用于隱式轉換
 15     explicit minHeap(const vector<Comparable>& items);
 16     
 17     bool isEmpty() const;
 18     Comparable min() const;
 19     
 20     void insert(const Comparable& key); //插入關鍵字
 21     Comparable extractMin(); //獲得最小值并將其刪除
 22     void decreaseKey(int i,Comparable key); //增加優先級
 23     void increaseKey(int i,Comparable key); //相當于降低優先級
 24     void remove(int p); //刪除堆中位置p的結點，例如OS中非正常終止進程
 25 private:
 26     int heapsize;
 27     vector<Comparable> array;
 28     
 29     void build_heap(); //建堆
 30     void minHeapify(int hole); //從位置hole處向下篩選方法
 31 };
 32 
 33 template<typename Comparable>
 34 Comparable minHeap<Comparable>::min() const
 35 {
 36     return array[1];
 37 }
 38 
 39 template<typename Comparable>
 40 Comparable minHeap<Comparable>::extractMin() //獲取最小值并將其刪除
 41 {
 42     if (heapsize<1)
 43         cout << "error" << endl;
 44     else
 45     {
 46         Comparable min = array[1];
 47         array[1] = array[heapsize];
 48         --heapsize;
 49         minHeapify(1);
 50         return min;
 51     }
 52 }
 53 
 54 template<typename Comparable>
 55 void minHeap<Comparable>::decreaseKey(int i,Comparable key)
 56 {
 57     if (key>array[i])
 58         cout << "new key is larger than current key!" << endl;
 59     else
 60     {
 61         array[i] = key;
 62         for(; i>1 && array[i]<array[i/2]; i /= 2)
 63             array[i] = array[i/2];
 64         array[i] = key;
 65     }
 66 }
 67 
 68 template<typename Comparable>
 69 void minHeap<Comparable>::increaseKey(int i,Comparable key)
 70 {
 71     if (key<array[i])
 72         cout << "new key is smaller than current key!" << endl;
 73     else
 74     {
 75         array[i] = key;
 76         minHeapify(i);
 77     }
 78 }
 79 
 80 template<typename Comparable>
 81 void minHeap<Comparable>::insert(const Comparable& key)
 82 {
 83     if(heapsize == array.size()-1)
 84         array.resize(array.size()*2);
 85     int hole = ++heapsize;
 86     for(; hole>1 && key<array[hole/2]; hole /=2) //向上過濾篩選
 87         array[hole] = array[hole/2];
 88     array[hole] = key;
 89 }
 90 
 91 template<typename Comparable>
 92 void minHeap<Comparable>::minHeapify(int hole) //向下過濾篩選
 93 {
 94     Comparable tmp = array[hole];
 95     for (int child = 2*hole; child <= heapsize; child *= 2)
 96     {
 97         if (child<heapsize && array[child] > array[child+1])
 98             ++child;
 99         if (tmp < array[child])
100             break;
101         array[hole] = array[child];
102         hole = child;
103     }
104     array[hole] = tmp;
105 }
106 
107 template<typename Comparable>
108 void minHeap<Comparable>::build_heap() //建堆
109 {
110     for (int i = heapsize/2; i>0; --i) //從下往上篩選
111         minHeapify(i);
112 }
113 
114 
115 template<typename Comparable>
116 void minHeap<Comparable>::remove(int p) //刪除位置p處的元素
117 {
118     array[p] = array[heapsize];
119     --heapsize;
120     Comparable key = array[p];
121     if (key>array[p/2]) //向下篩選
122         minHeapify(p);
123     else //向上篩選
124         for (; p>1,array[p/2]>key; p /=2)
125             array[p] = array[p/2];
126         array[p] = key;
127 }
128 
129 template<typename Comparable> // 構造函數之一
130 minHeap<Comparable>::minHeap(int campacity)
131 :    heapsize(campacity)
132 {
133     array.resize(campacity+10);
134 }
135 
136 template<typename Comparable> //構造函數之二
137 minHeap<Comparable>::minHeap(const vector<Comparable>& items)
138 :array(items.size()+10), heapsize(items.size())
139 {
140     for (int i = 0; i<items.size(); ++i)
141         array[i+1] = items[i];
142     build_heap();
143 }
144 
145 template<typename Comparable> //判斷堆是否為空
146 bool minHeap<Comparable>::isEmpty() const
147 {
148     if (0 == heapsize)
149         return true;
150     return false;
151 }
152 
153 
154 ////
155 template<typename Comparable>
156 void dumpContents(const string& msg, minHeap<Comparable>& pq)
157 {
158     cout << msg << ":" << endl;
159     while (!pq.isEmpty())
160     {
161         cout << pq.extractMin() << endl;
162     }
163 }
164 
165 int main()
166 {
167     //測試一
168     /*minHeap<int> minPQ;
169     minPQ.insert(4);
170     minPQ.insert(3);
171     minPQ.insert(2);
172     minPQ.insert(6);
173     minPQ.insert(1);
174     minPQ.increaseKey(4,20);
175     minPQ.decreaseKey(3,0);
176     minPQ.remove(5);
177     dumpContents("minPQ",minPQ);*/
178     
179     //測試二
180     vector<int> a;
181     a.push_back(10);
182     a.push_back(9);
183     a.push_back(7);
184     a.push_back(6);
185     a.push_back(5);
186     a.push_back(4);
187     minHeap<int> minpQ(a);
188     dumpContents("minPQ",minpQ);
189     return 0;
190 }

轉載于:https://www.cnblogs.com/lyfruit/archive/2012/12/29/2839311.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/376960.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/376960.shtml
英文地址，請注明出處：http://en.pswp.cn/news/376960.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！