这两年一直埋首在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 }
参考： 算法导论