STL---heap概述，make_heap,sort_heap,pop_heap,push_heap_BIG_GENERAL_DD的博客-程序员秘密

技术标签：查漏补缺

heap并不属于STL容器组件，它分为 max heap 和min heap，在缺省情况下，max-heap是优先队列（priority queue）的底层实现机制。

而这个实现机制中的max-heap实际上是以一个vector表现的完全二叉树（complete binary tree）。

二叉堆（binary heap）就是i一种完全二叉树。也即是。整棵二叉树除了最底层的叶节点以外，都是填满的，而最低层的叶子结点必须是从左到右不留空隙。

至于max-heap和min-heap，前者的任何一个父亲结点都必须大于等于他的任意子结点，而后者相反。

上面表示的是一颗完全二叉树。

下面我们利用数组来隐式表达这棵数：

第0号元素保留，从arry[1]开始保存A，这时候我们可以轻易的看到：

位于位置i的某个结点arry[i]，他的左子结点必然在arry[2*i]中，右子结点必然位于arry[2*i+1]，其父亲结点必然位于arry[i/2]处。

这种数组表达的方式我们称为隐式表达。

当然由于arry大小是静态的，不能动态添加元素，我们可以使用vector来实现。

heap-算法：

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(RamdomAccessIteraor first,RamdomAccessIteraor end)接受两个随机迭代器作为参数。表示操作的范围。

注意这个排序执行的前提是，在一个堆上执行。

make_heap()算法：

建立一个堆。很简单吧。接受的参数同上。

下面我们来看测试实例吧：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	int ia[9]={0,1,2,3,4,8,9,3,5};
	vector<int> ivec(ia,ia+9);  //底层我们使用vector来实现，可以动态添加元素。 
	
	make_heap(ivec.begin(),ivec.end());
	for(int i=0;i!=ivec.size();i++)cout<<ivec[i]<<" ";
	cout<<endl;
	
	ivec.push_back(7);
	push_heap(ivec.begin(),ivec.end());//这里可以用make_heap替换。 
	for(int i=0;i!=ivec.size();i++)cout<<ivec[i]<<" ";
	cout<<endl;
	
	pop_heap(ivec.begin(),ivec.end());
	cout<<ivec.back()<<endl;
	ivec.pop_back();
	for(int i=0;i!=ivec.size();i++)cout<<ivec[i]<<" ";
	cout<<endl;
	
	sort_heap(ivec.begin(),ivec.end());
	for(int i=0;i!=ivec.size();i++)cout<<ivec[i]<<" ";
	cout<<endl;
	
	{
		int ia[9]={0,1,2,-1,4,8,9,3,5};//底层我使用数组来完成。 
		make_heap(ia,ia+9);
		for(int i=0;i<9;i++)cout<<ia[i]<<" ";
		cout<<endl;
		sort_heap(ia,ia+9);
		for(int i=0;i<9;i++)cout<<ia[i]<<" ";
		cout<<endl;
	}
	
	
	return 0;
}

STL---heap概述，make_heap,sort_heap,pop_heap,push_heap

本文链接：https://blog.csdn.net/wangdd_199326/article/details/78410931

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

[.Net码农]BulkCopytoSQL做批量导入_妹子把我们叫二货的博客-程序员秘密

//批量导入功能 public string BulkCopytoSQL(DataTable DataSoure, string dataTableName ) { string result = "成功"; try { //额外添加列 string workersNo = Reque

在二叉树中找到一个节点的后继节点_在含有27个节点的二叉树上寻找35的节点_beOkWithAnything的博客-程序员秘密

二叉树中一个节点的后继节点指的是，二叉树的中序遍历的序列中的下一个节点。链接：https://www.nowcoder.com/questionTerminal/c37ec6a9e4084b9c943be2d3a369e177来源：牛客网输入描述: 第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。以下 n 行每行四个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa没有左儿子，rch同

[Hyper-v]删除系统保留分区，修复克隆win7/win8虚拟磁盘后无法引导问题_hyper 删除 gpup分区_CG李大仁的博客-程序员秘密

使用Hyper-v克隆Windows7／windows8的虚拟磁盘之后，发现系统无法正常引导（Boot），并且克隆之后的硬盘的大小小于原始硬盘的大小。调查后发现：Windows7之后为了保证系统数据的安全，Wndows引入了BitLocker数据加密机制，新安装的操作系统时会自动创建一个100MB的系统保留分区，使用BitLocker方式加密Windows系统的引导信息，这一分区的数据不能直接克隆

cordova app强制横屏，config.xml配置横屏_天马3798的博客-程序员秘密

cordova app强制横屏，config.xml配置横屏配置代码：<preference name="Orientation" value="landscape" />Orientation的值Orientation的默认值是default。可使用的值有：default, landscape, portraitOrientation可以将设备锁...

Linux 路由跟踪指令traceroute命令_Li--AiTao的博客-程序员秘密

文所有命令实施的大前提是：你现在能够上网。稍有计算机常识的人都知道ping命令，是用来检查自己的主机是否与目标地址接通，自己的主机与目标地址的通讯包通讯速率，所谓的通讯包也就是那些什么TCP/IP，UDP包，这里说得通俗一点，比如，就拿这个IT网站csdn来测试一下，则得到如下效果：但是路由跟踪指令traceroute，在windows则是tracert，对于非计算机网络内行，就不太知道这是干什么...

.Net 下未捕获异常的处理_eaglet的博客-程序员秘密

.Net 下未捕获异常的处理作者：Eaglet 随着.Net技术的发展，.Net技术被逐渐应用到很多大型的应用软件项目中。这些项目的规模越来越大，很多项目中除了自己的代码外还引用了很多第三方的.net组件。同时很多项目又被应用到很多关键的部门，软件系统的稳定性越来越至关重要。由于.Net框架提供了非常强大的异常处理机制，同时对一些非托管代码很难控制的系统问题比如指针越

STL---heap概述，make_heap,sort_heap,pop_heap,push_heap_BIG_GENERAL_DD的博客-程序员秘密

heap并不属于STL容器组件，它分为 max heap 和min heap，在缺省情况下，max-heap是优先队列（priority queue）的底层实现机制。

heap-算法：

push_heap()：新添加一个元素在末尾，然后重新调整堆序。也就是把元素添加在底层vector的end()处。

sort_heap（）算法：

make_heap()算法：

智能推荐

[.Net码农]BulkCopytoSQL做批量导入_妹子把我们叫二货的博客-程序员秘密

在二叉树中找到一个节点的后继节点_在含有27个节点的二叉树上寻找35的节点_beOkWithAnything的博客-程序员秘密

[Hyper-v]删除系统保留分区，修复克隆win7/win8虚拟磁盘后无法引导问题_hyper 删除 gpup分区_CG李大仁的博客-程序员秘密

cordova app强制横屏，config.xml配置横屏_天马3798的博客-程序员秘密

Linux 路由跟踪指令traceroute命令_Li--AiTao的博客-程序员秘密

.Net 下未捕获异常的处理_eaglet的博客-程序员秘密

随便推点

全网首发，你没见过的实用需求！用Python实现vlookup函数的 “一表引用” 和 “跨表引用”_python 表格引用其他列表的数据_数据分析与统计学之美的博客-程序员秘密

Fedora 17无法用root账户登录解决方法_始终不够的博客-程序员秘密

【本人秃顶程序员】【程序人生】为什么说 Java 程序员必须掌握 Spring Boot_本人秃顶程序员的博客-程序员秘密

C# 二进制文件内容读取类BinaryReader(读取图片文件或者二进制文本)_binaryreader c#_ClementQL的博客-程序员秘密

Oracle入门（十四.11）之使用显式游标属性_茅坤宝骏氹的博客-程序员秘密

剑指Offer-队列部分_Jason kyon的博客-程序员秘密

推荐文章

热门文章

相关标签