首页 / C++ / c++ heap学习
c++ heap学习
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了c++ heap学习,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2891字,纯文字阅读大概需要5分钟。
内容图文
![c++ heap学习](/upload/InfoBanner/zyjiaocheng/1277/1a8a9741ad49430c8667a1830bffc706.jpg)
heap并不属于STL容器组件,它分为 max heap 和min heap,在缺省情况下,max-heap是优先队列(priority queue)的底层实现机制。
而这个实现机制中的max-heap实际上是以一个vector表现的完全二叉树(complete binary tree)。
二叉堆(binary heap)就是i一种完全二叉树。也即是。整棵二叉树除了最底层的叶节点以外,都是填满的,而最低层的叶子结点必须是从左到右不留空隙。
至于max-heap和min-heap,前者的任何一个父亲结点都必须大于等于他的任意子结点,而后者相反。
《在这里值得一提的是》,heap对于map/unordered_map的排序(大小排序方式)是根据key值来排序的。
操作:
push_heap():新添加一个元素在末尾,然后重新调整堆序。也就是把元素添加在底层vector的end()处。
该算法必须是在一个已经满足堆序的条件下,添加元素。该函数接受两个随机迭代器,分别表示first,end,区间范围。
关键是我们执行一个siftup()函数,上溯函数来重新调整堆序。
pop_heap()这个算法跟push_heap类似,参数一样。不同的是我们把堆顶元素取出来,放到了数组或者是vector的末尾,用原来末尾元素去替代,然后end迭代器减1,执行siftdown()下溯函数来重新调整堆序。
注意算法执行完毕后,最大的元素并没有被取走,而是放于底层容器的末尾。如果要取走,则可以使用底部容器(vector)提供的pop_back()函数。
sort_heap()算法:既然每次pop_heap可以获得堆中最大的元素,那么我们持续对整个heap做pop_heap操作,每次将操作的范围向前缩减一个元素。
sort_heap() 算法:接受两个随机迭代器作为参数。表示操作的范围。
make_heap()算法:建立一个堆。很简单吧。接受的参数同上。
#include <iostream> #include <algorithm> // make_heap(), pop_heap(), push_heap() #include <vector> usingnamespace std; void printVector(vector<int> &num) { for(int i = 0; i < num.size(); i++) cout<<num[i]<<""; cout<<endl; } int main() { // initint arr[] = {5,1,6,9,4,3}; vector<int> num(arr,arr+6); printVector(num); // build make_heap(num.begin(),num.end()); printVector(num); // 9 5 6 1 4 3 默认大顶堆 // get the biggest number // 从vector的角度来取得 cout<<num[0]<<endl; // 9 // or num.front(); cout<<num.front()<<endl; // 9 // delete 堆顶,即最大的元素 // 返回值为 void // 将堆顶的元素放到最后一个位置上 // 弹出一个元素后,剩下的又重建了 heap,仍保持heap的性质 pop_heap(num.begin(),num.end()); printVector(num); // 6 5 3 1 4 9 // vector 删除末尾元素 num.pop_back(); printVector(num); num.push_back(7); //首先在vector上扩容,增加一个元素到尾部 printVector(num); // 6 5 3 1 4 7 push_heap(num.begin(),num.end()); // 指定区间的最后一个元素加入堆中并使整个区间成为一个新的堆。注意前提是最后一个元素除外的所有元素已经构成一个堆。 printVector(num); // 7 5 6 1 4 3 // 判断是否为堆bool ret = is_heap(num.begin(),num.end()); cout<<ret<<endl; num.push_back(9); printVector(num); // 7 5 6 1 4 3 9 cout<< is_heap(num.begin(),num.end()) <<endl; push_heap(num.begin(),num.end()); printVector(num); // 9 5 7 1 4 3 6 sort_heap(num.begin(),num.end()); printVector(num); // 1 3 4 5 6 7 9} // 小顶堆 #include <iostream> #include <vector> #include <algorithm> usingnamespace std; class greater_class{ public: booloperator()(int a, int b) { return a > b; } }; int main() { // initint arr[] = {5,1,6,9,4,3}; vector<int> num(arr,arr+6); printVector(num); make_heap(num.begin(), num.end(), greater_class()); printVector(num); // 1 4 3 9 5 6 num.push_back(2); printVector(num); // 1 4 3 9 5 6 2 push_heap(num.begin(),num.end(),greater_class()); printVector(num); // 1 4 2 9 5 6 3 while (num.size()) { pop_heap(num.begin(),num.end(),greater_class()); long min = num.back(); num.pop_back(); cout << min << std::endl; } // 1 2 3 4 5 6 9 }
原文:http://www.cnblogs.com/home123/p/7440001.html
内容总结
以上是互联网集市为您收集整理的c++ heap学习全部内容,希望文章能够帮你解决c++ heap学习所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。