文章目录

0、误区！

1、堆排序排完后的堆和大顶堆、小顶堆不是一个概念！
2、堆分为大顶堆和小顶堆，即要么大顶堆（大根堆/最大堆），要么小顶堆。
3、对于堆，堆的根节点一定是堆中所有节点的最大值或者最小值。
4、大顶堆只是说这个堆总每一个节点满足：每一个节点大于或者等于其左右娃。并非这个堆一定是从大到小的序列。
5、所以才必须要有堆排序呀！堆排序排完了之后的，才一定是一个有序的序列。
6、堆实际上是用数组或者vector表现出来的一颗具有特殊结构的完全二叉树。

1、heap

头文件#include <algorithm>,STL在中实现了对存储在数组或vector中的元素进行堆操作的函数，包括make_heap, pop_heap, push_heap, sort_heap。
【两层：上层heap，底层vector(或数组)】，即用数组或vector数据容器来实现堆。
默认情况下是max-heap，该大顶堆实际上是以一个vector表现的完全二叉树。

2、heap操作的四个函数：

  • 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：

  1. max_heap.push_back(15);
  2. 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()，从底层容器中删掉原堆顶元素。

  1. pop_heap(max_heap.begin(), max_heap.end());//取出了堆顶元素（也叫删除堆顶元素），放到了底层容器的末尾，原来末尾的元素替代堆顶，end迭代器减1，重新siftdown了堆
  2. 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

3、例1:基本操作的使用

底层数据容器：vector
1、
建立小顶堆min；
在小顶堆中插入元素；
删除小顶堆的元素（删的是h[0]）；
小顶堆下的堆排序——> 降序的序列。

  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  5. using namespace std;
  7. void printHeap(vector<int> &v){
  8.     for(vector<int>::iterator it= v.begin();it!=v.end();++it){
  9.         cout<< *it <<" ";
  10.     }
  11.     cout<<"\n"<<endl;
  12. }
  14. int main()
  15. {
  16.     vector<int> min={10,30,22,6,15,9};
  18.     //建立小顶堆
  19.     make_heap(min.begin(), min.end(), greater<int>());
  20.     printHeap(min);//6 10 9 30 15 22
  22.     //插入元素
  23.     min.push_back(20);
  24.     push_heap(min.begin(),min.end(), greater<int>());//该算法前提：必须在堆的条件下
  25.     printHeap(min); //6 10 9 30 15 22 20   仍为小顶堆
  27.     //删除堆顶元素
  28.     pop_heap(min.begin(),min.end(), greater<int>());
  29.     printHeap(min);//9 10 20 30 15 22 6  不为小顶堆 这个pop_heap操作后，实际上是把堆顶元素放到了末尾
  30.     min.pop_back();//这才彻底在底层vector数据容器中删除
  31.     printHeap(min);//9 10 20 30 15 22  仍为小顶堆
  33.     //堆排序  保持greater，小顶堆，得到的是降序
  34.     sort_heap(min.begin(),min.end(), greater<int>());//试了用less，结果杂乱无章
  35.     printHeap(min);//30 22 20 15 10 9 注意结果是降序的哦!!!其实是调用了很多次pop_heap(...,greater..)，每一次都把小顶堆堆顶的元素往末尾放，没放一次end迭代器减1
  37.     return 0;
  38. }

2、大顶堆，以及堆排序为升序的例子
把上面code里所有的第三个参数改为less<int>()。

4、应用：数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
解决：
采用大顶堆和小顶堆实现。把数据分为两部分，左边部分整体上要小于右边部分。
左边部分为大顶堆，右边部分为小顶堆，往两边堆中不断插入数据。
定：当数据总数为偶数时，插入到min堆，总数为奇数时，插入到max堆。插入过程中要保证左边部分总体小于右边部分，要不断调整。最后，总数为偶数时候，中位数为max堆顶元素和min堆顶元素之和的平均，为奇数，则为min堆的堆顶元素。

  1. class Solution {
  2. private:
  3.     vector<int> max;//大顶堆（左部分数据，堆顶为堆的最大值(为max[0])）
  4.     vector<int> min;//小顶堆（右部分数据，堆顶为堆的最小值(为min[0])）
  5. public:
  6.     void Insert(int num)
  7.     {
  8.         if(((max.size()+min.size())&1)==0)//总数偶数
  9.         {   /*来了一个数，此时总数为偶数，原计划加入到小顶堆，（奇数则到大顶堆，保证两边均匀分配）
  11.               但是要保证小顶堆的最小值一直大于大顶堆的最大值（即小顶堆的数大于大顶堆的）：
  12.                   if num<大顶堆的最大值：
  13.                       则反而插入到大顶堆中（大顶堆元素多了1个）；
  14.                       则把大顶堆的最大值删掉，重新插入到小顶堆去;
  15.                   else:
  16.                       插入元素到小顶堆去。
  17.             */
  18.             if(max.size()>0 && num< max[0])
  19.             {
  20.                 //添加num到大顶堆
  21.                 max.push_back(num);
  22.                 push_heap(max.begin(),max.end(),less<int>());//仿函数less保证插入后仍为大顶堆
  24.                 //把大顶堆里的最大值删掉，添加到小顶堆里面去
  25.                 num= max[0];
  26.                 pop_heap(max.begin(),max.end(),less<int>());
  27.                 max.pop_back();
  29.                 min.push_back(num);//push_heap前必须push_back到底层容器
  30.                 push_heap(min.begin(), min.end(), greater<int>());//仿函数greater保证插入后仍为小顶堆
  31.             }else
  32.             {
  33.                 min.push_back(num);          //这块，和上面有公共代码，可以化简
  34.                 push_heap(min.begin(),min.end(),greater<int>());
  35.             }
  36.         }else//总数奇数，原计划送到大顶堆
  37.         {
  38.             if(min.size()>0 && num>min[0])
  39.             {
  40.                 min.push_back(num);
  41.                 push_heap(min.begin(),min.end(),greater<int>());
  43.                 num=min[0];
  44.                 pop_heap(min.begin(), min.end(),greater<int>());
  45.                 min.pop_back();
  47.                 max.push_back(num);
  48.                 push_heap(max.begin(),max.end(), less<int>());
  49.             }else
  50.             {
  51.                 max.push_back(num);
  52.                 push_heap(max.begin(),max.end(),less<int>());
  53.             }
  54.         }
  55. }
  57.     double GetMedian()
  58.     { 
  59.         double median=0;
  60.         if((max.size()+min.size())==0)
  61.             return 0;
  63.         if(((max.size()+min.size()) &1)==0)
  64.         {
  65.             median= ((double)max[0]+(double)min[0])/2;
  66.         }else
  67.         {
  68.             median= min[0];
  69.         }
  70.         return median;
  71.     }
  72. };