C++ 堆的应用

今天做剑指offer的一道题，找最小的k个数。利用最大堆的思路来求解。这里整理一下C++中堆的用法
可参考http://www.cplusplus.com/reference/algorithm/push_heap/

建堆make_heap

#include <iostream>
#include <algorithm>
#include <vector>

//将[start, end)进行堆排序，默认使用less，将最大元素放第一个
int num[] = {1,3,4,5,9,12};
vector<int> vec(num, num+6);
make_heap( vec.begin(), vec.end() );
cout << "initial max heap is : " << vec.front() << endl;   //输出12

插入push_heap

//先将元素插入尾部；然后进行堆排序
int i = 20;
vec.push_back(i);
push_heap( vec.begin(), vec.end() );
cout << "after push the max heap is : " << vec.front() << endl;   //输出20

删除pop_heap()

//将front(即第一个最大元素)移动到end前部;然后把剩下元素pop出去
pop_heap( vec.begin(), vec.end() );
vec.pop_back();
cout << "after pop the max heap is : " << vec.front() << endl;   //输出12

排序sort_heap()

sort_heap(vec.begin(), vec.end());
cout << "final sort range is: ";
for(unsigned i;i<vec.size();++i)
    cout << ' ' << vec[i];
cout << '\n' <<endl;