c++ reference: http://www.cplusplus.com/reference/algorithm/make_heap/
heap并不属于STL容器组件，它分为 max heap 和min heap，在缺省情况下，max-heap是优先队列（priority queue）的底层实现机制。
而这个实现机制中的max-heap实际上是以一个vector表现的完全二叉树（complete binary tree）。
二叉堆（binary heap）就是i一种完全二叉树。也即是。整棵二叉树除了最底层的叶节点以外，都是填满的，而最低层的叶子结点必须是从左到右不留空隙。
至于max-heap和min-heap，前者的任何一个父亲结点都必须大于等于他的任意子结点，而后者相反。
下面我们利用数组来隐式表达这棵数：
第0号元素保留，从arry[1]开始保存A，这时候我们可以轻易的看到：
位于位置i的某个结点arry[i]，他的左子结点必然在arry[2*i]中，右子结点必然位于arry[2*i+1]，其父亲结点必然位于arry[i/2]处。
这种数组表达的方式我们 称为 隐式表达。
当然由于arry大小是静态的，不能动态添加元素，我们可以使用vector来实现。
heap-算法：
1. push_heap()，新添加一个元素在末尾，然后重新调整堆序。也就是把元素添加在底层vector的end()处。
该算法必须是在一个已经满足堆序的条件下，添加元素。该函数接受两个随机迭代器，分别表示first,end,区间范围。
关键是我们执行一个siftup()函数，上溯函数来重新调整堆序。具体的函数机理很简单，可以参考我的编程珠玑里面堆的实现的文章。
2. pop_heap()，这个算法跟push_heap类似，参数一样。不同的是我们把堆顶元素取出来，放到了数组或者是vector的末尾，用原来末尾元素去替代，
然后end迭代器减1，执行siftdown()下溯函数来重新调整堆序。
注意算法执行完毕后，最大的元素并没有被取走，而是放于底层容器的末尾。如果要取走，则可以使用底部容器（vector）提供的pop_back()函数。
3. sort_heap()，既然每次pop_heap可以获得堆中最大的元素，那么我们持续对整个heap做pop_heap操作，每次将操作的范围向前缩减一个元素。
当整个程序执行完毕后，我们得到一个非降的序列。
同理，sort_heap(RamdomAccessIteraor first,RamdomAccessIteraor end)接受两个随机迭代器作为参数。表示操作的范围。
注意这个排序执行的前提是，在一个堆上执行。执行完之后序列也就失去了堆的性质。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<deque> #include<map> #include<set> #include <sstream> using namespace std; void outHeap(vector<int> v){ for(int i=0; i<v.size(); ++i) cout<<v[i]<<" "; cout<<endl; } int main(){ int myints[] = {10,20,30,5,15}; vector<int> v(myints,myints+5); cout<<"建堆:"<<endl; make_heap(v.begin(), v.end()); outHeap(v); cout<<endl; cout<<"往堆里插入一个元素:"<<endl; v.push_back(100); push_heap(v.begin(), v.end()); outHeap(v); cout<<endl; cout<<"弹出堆顶元素，输出下一个堆顶元素:" <<endl; cout<<"当前堆顶元素: "<<v.front()<<endl; pop_heap(v.begin(), v.end()); v.pop_back(); cout<<"下一个堆顶元素: "<<v.front()<<endl; cout<<endl; cout<<"排序堆:"<<endl; sort_heap(v.begin(), v.end());//默认从小到大 //sort_heap(v.begin(), v.end(), greater<int>()); outHeap(v); //通过multiset实现最小堆 cout<<endl<<"通过multiset实现最小堆:"<<endl; multiset<int> mst(myints,myints+5); for(multiset<int>::iterator it = mst.begin(); it!=mst.end(); ++it) cout<<*it<<" "; cout<<endl; return 0; }
4.一道很经典的题目就是在1亿个数中找到最大的前100个数，这是一道堆应用题，找最大的前100个数，那么我们就创建一个大小为100的最小化堆，每来一个元素就与堆顶元素比较，因为堆顶元素是目前前100大数中的最小数，前来的元素如果比该元素大，那么就把原来的堆顶替换掉并重新调整堆。
5.例题：lintcode 滑动窗口的中位数 : http://www.lintcode.com/zh-cn/problem/sliding-window-median/
//最无脑的解法....
class Solution { public: /** * @param nums: A list of integers. * @return: The median of the element inside the window at each moving */ vector<int> medianSlidingWindow(vector<int> &nums, int k) { vector<int>v; vector<int> res; if (k > nums.size() || k == 0) return res; for(int i=0; i<k; ++i) v.push_back(nums[i]); sort(v.begin(), v.end()); res.push_back(v[(k-1)/2]); for(int i=k; i<nums.size(); ++i){ v.erase(lower_bound(v.begin(), v.end(), nums[i-k])); v.insert(lower_bound(v.begin(), v.end(), nums[i]), nums[i]); res.push_back(v[(k-1)/2]); } return res; } };
//使用multiset进行优化（内部以平衡二叉树），感觉和上面的"最脑的解法差不多"， 只不过是将一个有序的序列分成左右连个连续的序列，左边序列的最后一个就是中位数
class Solution { public: /** * @param nums: A list of integers. * @return: The median of the element inside the window at each moving */ vector<int> medianSlidingWindow(vector<int> &nums, int k) { // write your code here vector<int> res; if (k > nums.size() || k == 0) return res; multiset<int> left, right; //init heaps by first kth elements in nums for (int i = 0; i < k; ++i) { left.insert(nums[i]); } while (left.size() > (k + 1) / 2) { right.insert(*left.rbegin()); left.erase(left.find(*left.rbegin())); } res.push_back(*left.rbegin()); //slide window for (int i = k; i < nums.size(); ++i) { //delete the leftmost element in window from heaps if (nums[i-k] > res.back()) right.erase(right.find(nums[i-k])); else left.erase(left.find(nums[i-k])); //insert new element into heaps if (!left.empty() && nums[i] <= *left.rbegin()) left.insert(nums[i]); else right.insert(nums[i]); //adjust heaps so that the left heap contains (k + 1) / 2 elements if (left.size() < (k + 1) / 2) { left.insert(*right.begin()); right.erase(right.begin()); } else if (left.size() > (k + 1) / 2) { right.insert(*left.rbegin()); left.erase(left.find(*left.rbegin())); } res.push_back(*left.rbegin()); } return res; } };
