1、堆排序排完后的堆和大顶堆、小顶堆不是一个概念！
2、堆分为大顶堆和小顶堆，即要么大顶堆（大根堆/最大堆），要么小顶堆。
3、对于堆，堆的根节点一定是堆中所有节点的最大值或者最小值。
4、大顶堆只是说这个堆总每一个节点满足：每一个节点大于或者等于其左右娃。并非这个堆一定是从大到小的序列。
5、所以才必须要有堆排序呀！堆排序排完了之后的，才一定是一个有序的序列。
6、堆实际上是用数组或者vector表现出来的一颗具有特殊结构的完全二叉树。
头文件#include <algorithm>,STL在<algorithm.h>中实现了对存储在数组或vector中的元素进行堆操作的函数，包括make_heap, pop_heap, push_heap, sort_heap。
【两层：上层heap，底层vector(或数组)】，即用数组或vector数据容器来实现堆。
默认情况下是max-heap，该大顶堆实际上是以一个vector表现的完全二叉树。
- make_heap( )：建立堆（要么大顶堆，要么小顶堆）
- push_heap( ): 在堆中添加元素
- pop_heap( ): 在堆中删除元素
- sort_heap( ): 堆排序
相关参数：
_First, _Last：可以随机访问的迭代器/ 指针
_Comp: 比较函数（仿函数）,其规则——如果函数的第一个参数小于第二个参数应返回true，否则返回false。默认less
使用建议：
大顶堆，就每一个函数都加上第三个参数less<int>()，假如元素是int类型的；
小顶堆，就每一个函数都加上第三个参数greater<int>()，假如元素是int类型的，一直加上，一直一致。
建立堆
make_heap(_First, _Last, _Comp)
默认是建立大最大堆的。
在堆中添加元素
push_heap(_First, _Last，_Comp)
要先在底层容器（数组或vector）里加入数据，再调用push_heap()。
实现细节：（1）添加元素到vector的尾部；（2）重新调整堆。
该算法必须是在满足堆序的条件下，添加元素。
如，插入15到当前的大根堆里，vector容器名字为max_heap：
max_heap.push_back(15);
push_heap(max_heap.begin(), max_heap.end());在堆中删除元素
pop_heap(_First, _Last，_Comp)
实现细节：（1）删除堆顶元素；（2）用尾部元素替代max_heap[0]；（3）重新调整堆。
(pop_heap操作实际上是我们把堆顶元素取出来，放到了数组或vector容器的末尾，用原来的末尾元素去替代，然后end迭代器减1，执行siftdown()下溯函数来重新调整堆）
注意算法执行完毕后，最大的元素并没有被取走，而是放于底层容器的末尾。如果要取走，则可以使用底部容器（vector）提供的pop_back()函数。
pop_heap()操作后，再调用max_heap.pop_back()，从底层容器中删掉原堆顶元素。
pop_heap(max_heap.begin(), max_heap.end());//取出了堆顶元素（也叫删除堆顶元素），放到了底层容器的末尾，原来末尾的元素替代堆顶，end迭代器减1，重新siftdown了堆
max_heap.pop_back();//从底层容器（数组或vector）中删除了元素堆排序
sort_heap(_First, _Last，_Comp)
既然每次pop_heap可以获得堆顶的元素（假如是大顶堆，每次都获得最大的元素，取出放到了底层容器的末尾），那么我们持续对整个heap做pop_heap操作，每次讲操作的范围向前缩减一个元素（就是每次end迭代器减1）。最终我们可以获得一个递增的序列。
注意：这个排序是在一个堆上进行的。
关于堆排序，可以看看这个博客<<白话经典算法系列之七 堆排序>> https://blog.csdn.net/morewindows/article/details/6709644
4、例1:基本操作的使用
底层数据容器：vector
1、
建立小顶堆min；
在小顶堆中插入元素；
删除小顶堆的元素（删的是h[0]）；
小顶堆下的堆排序——> 降序的序列。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void printHeap(vector<int> &v){
for(vector<int>::iterator it= v.begin();it!=v.end();++it){
cout<< *it <<" ";
}
cout<<"
"<<endl;
}
int main()
{
vector<int> min={10,30,22,6,15,9};
//建立小顶堆
make_heap(min.begin(), min.end(), greater<int>());
printHeap(min);//6 10 9 30 15 22
//插入元素
min.push_back(20);
push_heap(min.begin(),min.end(), greater<int>());//该算法前提：必须在堆的条件下
printHeap(min); //6 10 9 30 15 22 20 仍为小顶堆
//删除堆顶元素
pop_heap(min.begin(),min.end(), greater<int>());
printHeap(min);//9 10 20 30 15 22 6 不为小顶堆 这个pop_heap操作后，实际上是把堆顶元素放到了末尾
min.pop_back();//这才彻底在底层vector数据容器中删除
printHeap(min);//9 10 20 30 15 22 仍为小顶堆
//堆排序 保持greater，小顶堆，得到的是降序
sort_heap(min.begin(),min.end(), greater<int>());//试了用less，结果杂乱无章
printHeap(min);//30 22 20 15 10 9 注意结果是降序的哦!!!其实是调用了很多次pop_heap(...,greater..)，每一次都把小顶堆堆顶的元素往末尾放，没放一次end迭代器减1
return 0;
}2、大顶堆，以及堆排序为升序的例子
把上面code里所有的第三个参数改为less<int>()。
4、应用：数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
解决：
采用大顶堆和小顶堆实现。把数据分为两部分，左边部分整体上要小于右边部分。
左边部分为大顶堆，右边部分为小顶堆，往两边堆中不断插入数据。
当数据总数为偶数时，插入到min堆，总数为奇数时，插入到max堆。插入过程中要保证左边部分总体小于右边部分，要不断调整。最后，总数为偶数时候，中位数为max堆顶元素和min堆顶元素之和的平均，为奇数，则为min堆的堆顶元素。
class Solution {
private:
vector<int> max;//大顶堆（左部分数据，堆顶为堆的最大值(为max[0])）
vector<int> min;//小顶堆（右部分数据，堆顶为堆的最小值(为min[0])）
public:
void Insert(int num)
{
if(((max.size()+min.size())&1)==0)//总数偶数
{ /*来了一个数，此时总数为偶数，原计划加入到小顶堆，（奇数则到大顶堆，保证两边均匀分配）
但是要保证小顶堆的最小值一直大于大顶堆的最大值（即小顶堆的数大于大顶堆的）：
if num<大顶堆的最大值：
则反而插入到大顶堆中（大顶堆元素多了1个）；
则把大顶堆的最大值删掉，重新插入到小顶堆去;
else:
插入元素到小顶堆去。
*/
if(max.size()>0 && num< max[0])
{
//添加num到大顶堆
max.push_back(num);
push_heap(max.begin(),max.end(),less<int>());//仿函数less保证插入后仍为大顶堆
//把大顶堆里的最大值删掉，添加到小顶堆里面去
num= max[0];
pop_heap(max.begin(),max.end(),less<int>());
max.pop_back();
min.push_back(num);//push_heap前必须push_back到底层容器
push_heap(min.begin(), min.end(), greater<int>());//仿函数greater保证插入后仍为小顶堆
}else
{
min.push_back(num); //这块，和上面有公共代码，可以化简
push_heap(min.begin(),min.end(),greater<int>());
}
}else//总数奇数，原计划送到大顶堆
{
if(min.size()>0 && num>min[0])
{
min.push_back(num);
push_heap(min.begin(),min.end(),greater<int>());
num=min[0];
pop_heap(min.begin(), min.end(),greater<int>());
min.pop_back();
max.push_back(num);
push_heap(max.begin(),max.end(), less<int>());
}else
{
max.push_back(num);
push_heap(max.begin(),max.end(),less<int>());
}
}
}
double GetMedian()
{
double median=0;
if((max.size()+min.size())==0)
return 0;
if(((max.size()+min.size()) &1)==0)
{
median= ((double)max[0]+(double)min[0])/2;
}else
{
median= min[0];
}
return median;
}
};