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;
}
};
