heap并不是属于STL中的containers,而是在<algorithm>下提供了相关的函数 make_heap,sort_heap,pop_heap,push_heap
函数的说明:
make_heap(_First, _Last, _Comp)
默认是建立最大堆的。对int类型,可以在第三个参数传入greater<int>() 得到最小堆,传入less<int>() 得到最大堆。
max-heap是优先队列(priority queue)的底层实现机制
max-heap实际上的实现可以是以一个vector表现的完全二叉树(complete binary tree)
Comp可以没有,那就是默认的maxheap
void make_heap (RandomAccessIterator first, RandomAccessIterator last);
first、last是两个随机的迭代器
// range heap example #include <iostream> // std::cout #include <algorithm> // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap #include <vector> // std::vector int main () { int myints[] = {10,20,30,5,15}; std::vector<int> v(myints,myints+5); std::make_heap (v.begin(),v.end()); std::cout << "initial max heap : " << v.front() << 'n'; std::pop_heap (v.begin(),v.end()); v.pop_back(); std::cout << "max heap after pop : " << v.front() << 'n'; v.push_back(99); std::push_heap (v.begin(),v.end()); std::cout << "max heap after push: " << v.front() << 'n'; std::sort_heap (v.begin(),v.end()); std::cout << "final sorted range :"; for (unsigned i=0; i<v.size(); i++) std::cout << ' ' << v[i]; std::cout << 'n'; return 0; } /* Output: initial max heap : 30 max heap after pop : 20 max heap after push: 99 final sorted range : 5 10 15 20 99 */
对于其它的heap函数,参数类型相同;
push_heap():把元素添加在底层vector的end()处,然后重新调整堆序(可以是执行一个siftup()函数);
pop_heap():把堆顶元素取出来,放到了数组或者是vector的末尾,用原来末尾元素去替代,然后end迭代器减1(后常跟vector的pop_back()操作),执行siftdown()下溯函数来重新调整堆序;
sort_heap():持续对整个heap做pop_heap操作,每次将操作的范围向前缩减一个元素,则可以得到排序好的序列。由于maxheap的top放在end处,所以sort_heap完之后顺序输出是非降序;
如上的算法需要在堆上进行操作
-------------------------------------------------------------
c++中的 priority_queue 数据结构底层使用了 heap, 所以也可以直接使用 priority_queue 来进行操作;
例如:数据流中的中位数——剑指offer
class Solution { public: void Insert(int num) { ++count; if(count&1){ //如果是奇数个数的元素,则先放入小顶堆,然后把小顶堆中的顶放到大顶堆中 min_heap.push(num); max_heap.push(min_heap.top()); min_heap.pop(); } else{ max_heap.push(num); min_heap.push(max_heap.top()); max_heap.pop(); } } double GetMedian() { if(count&1) return max_heap.top(); else return (max_heap.top()+min_heap.top())/2.0; } private: int count=0; priority_queue<int, vector<int>, less<int>> max_heap; priority_queue<int, vector<int>, greater<int>> min_heap; };
思想:两个堆轮着构建,复杂度 O(N),我们分析各自的复杂度;
- 直接排序,使用堆排序:O(N logN)
- 按照如上方法轮流构建:相当于3×(高度从0到log(N/2)的调整),相当于建立3个N/2大小的堆,O(N)
- 先构建N/2的堆,然后再构建另外一边的堆:相当于2×(高度从0到log(N/2)的调整),加上1个高度始终为log(N/2)的N/2次调整,所以总和比轮流构建多,复杂度为 O(N logN)
综上,采用轮流构建方式的复杂度占优
原文链接: https://www.cnblogs.com/zhang-qc/p/9096329.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/274749
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!