这两年一直埋首在C相关的代码中，都快忘记自己曾经热爱并赖以南征北战过的C++了，而且C++11出来那么久了，瞄了几眼，没练过都不敢说自己会C++了，
正好很多基础算法没正经的学习过，打算逐个（算法导论里的）用C++完成一遍好好练练手。（其实没那么多时间，能写几个就写几个啦，加之水平有限）
结果呢，一动起手来，还是觉得实现算法呢，还是C看起来舒服，C++反而不直观了，咋的整呢，管不了那么多了，写几行看看吧。
嗯，工欲善其事必先利其器，这里推荐编辑器code::blocks+mingw，清新好用，（当然vs更好用，不过你懂的啦），博主最后还是回到了eclipse的怀抱，refactor，debug功能比code::blocks好一点
堆有2种，最大堆和最小堆，其实就是一个比较因子的不同，算法描述是一样的。
heapify函数用来保持堆的特性，比如：
1、父节点总是大于子节点这是最大堆，反之，父节点总是小于子节点是最小堆
2、使用数组或者vector来实现堆比较方便，索引为i的元素，父节点就是i/2，左子节点是2*i，右子节点是2*i+1，i>=1。
3、插入一个新元素，在尾部插入最快，但是可能会破坏堆的特性，因此要注意重新保持堆的特性
另外，采用C++也有很多方便之处，比如有现成的functor可以使用。这只是个例子，请在实际工作中谨慎选择合适的数据结构或者容器。
1 #include <iostream> 2 #include <vector> 3 #include <cmath> 4 #include <cassert> 5 #include <functional> 6 7 using std::floor; 8 using std::swap; 9 using std::vector; 10 using std::greater; 11 using std::less; 12 13 template<typename _InIt, typename _Func> 14 void heapify(_InIt first, _InIt last, _InIt ite, _Func& Func) { 15 int i = ite - first; 16 _InIt it = ite; 17 18 if ((last-ite)>i && Func(*(ite+i), *(it))) { 19 it = ite + i; 20 } 21 22 if ((last-ite)>(i+1) && Func(*(ite+i+1), *(it))) { 23 it = ite + i + 1; 24 } 25 26 if (*it != *ite) { 27 swap(*ite, *it); 28 heapify(first, last, it, Func); 29 } 30 } 31 32 template<typename _InIt, typename _Func> 33 void build_heap(_InIt first, _InIt last, _Func &Func) { 34 int i = (int)floor((float)(last - first)/2); 35 for (; i>0; i--) { 36 heapify(first, last, first+i, Func); 37 } 38 } 39 40 template<typename _InIt, typename _Func> 41 void heap_sort(_InIt first, _InIt last, _Func &Func) { 42 for (_InIt it=(last-1); it != (first+1); --it) { 43 swap(*(first+1), *it); 44 heapify(first, it, first+1, Func); 45 } 46 } 47 48 template<typename T, typename _Func> 49 T heap_extract(vector<T> &v, _Func &Func) { 50 assert(v.size() >= 2); /* 因为多了一个填充元素 */ 51 52 typename vector<T>::iterator it = v.begin() + 1; /* 没有加typename gcc会报错 */ 53 T target = *(it); 54 55 v.erase(it); 56 heapify(v.begin(), v.end(), v.begin()+1, Func); 57 return target; 58 } 59 60 template<typename T, typename _Func> 61 void heap_increase_key(vector<T>& v, _Func &Func, int i, T key) { 62 v[i] = key; 63 while(i>1 && !Func(v[i/2], v[i])) { 64 swap(v[i], v[i/2]); 65 i >>= 1; 66 } 67 } 68 69 template<typename T, typename _Func> 70 void heap_insert(vector<T> &v, T key, _Func &Func) { 71 v.push_back(key); 72 heap_increase_key(v, Func, v.size()-1, key); 73 } 74 75 int main(int argc, char* argv[]) { 76 /* 堆的索引是1开始，所以第一个元素0是用来占位的 */ 77 int lst[] = {0,3,7,8,14,2,1,9,4,10,16}; 78 vector<int> v(lst, lst+11); 79 80 less<int> c; 81 build_heap(v.begin(), v.end(), c); 82 83 std::cout << heap_extract(v, c) << std::endl; 84 heap_sort (v.begin(), v.end(), c); 85 86 for (vector<int>::iterator it=v.begin(); it!=v.end(); ++it) { 87 std::cout << *it << " "; 88 } 89 std::cout << std::endl; 90 91 return 0; 92 }
参考： 算法导论