引入
平常,我们用堆最常见的就是随机地加入元素,随机地取最大值或最小值。这些基本的操作C++中的priority_queue和set都能很好的完成,而且C++中还有一个make_heap,效率较前面2个会更高。而且前面提到的STL都是采用红黑树实现的,很具有稳定性。
上面的堆虽然使用简单,但功能上还是有些局限。比如前面提到的堆都只能实现删除最值并没有办法删除指定的值。而且一般STL中的堆都是采用数据存储的,但父亲节点和儿子节点需要交换时,我们需要拷贝所存储的整个数据单元,但数据单元较大时,拷贝的效率就低了。因此,这里介绍一中堆变种,在堆中引入了映射。
定义
具有映射功能的堆称为双向映射堆。又因其常常是在二分堆的基础上实现的,所以也常常叫映射二分堆。
特点
映射二分堆其与普通堆不同的地方是它的节点并不真正保存数据单元本身,而是保存指向数据单元的指针。因此当需要交换父子节点的数据时,我们可以避免拷贝大量数据所消耗的时间。同时,映射二分堆还有一个功能,它可以根据具体的数据单元的索引来删除该单元,即使这个单元不是堆中的最值。
实现
在实现时,我们可以用数字 H[] 存储数据单元,然后采用数组 ind[i]=j 表示 H[i] 存放的是索引号为 j 的数据,mp[j]=i 表示索引索引为 j 的元素存储在 H[i] 中,这样就可以实现双向映射了。
(1) 插入堆,我们只需要将插入的元素放在堆尾,然后逐级调整,这个跟普通的二叉堆一样。
(2) 删除最值,也跟普通的二叉堆一样,先把堆中最后一个元素与最值对调,然后再调整堆。
(3) 删除固定索引的数据单元。我们可以先通过 mp[i],找到其在 H[] 中存放的位置,然后该位置的值跟堆最后一个元素对调,接着从该节点向上调整堆,此时得到的还不是一个正规的堆,还需要重新堆整个堆进行从上到下调整。
上面的3中操作中都提到了堆的调整,在调整时我们不需要拷贝数据单元,我们只需交换 ind[] 和 mp[] 2个数组的对应值即可。
原文地址:http://www.zhongsisi.com/stack-and-mapping/
分享到:
相关推荐
电子政务-极板流道分堆并接式电堆构成的直接甲醇燃料电池.zip
易语言文本栈源码,文本栈,IsEmpty,IsFull,Clear,Push,Pop,Remalloc,设置内存增量,GetTop,GetBottom,GetData,进入许可区,离开许可区,InitializeCriticalSection_临界许可,DeleteCriticalSection_临界许可,...
相关主题有:并查集算法,二分查找,栈,队列,背包,插入排序,选择排序,希尔排序,快速排序, 三切分快排,归并排序,堆排序,二分堆,二分查找树,红黑树,链表,线性哈希表,Graham扫描,kd树。 算法(二)...
这里是部分数据结构的实现, 二分堆, 红黑树, Splay树, 图, Set, Collection ...还有很多未完成. 之后有时间的话继续完成其他数据结构实现, 并实现一些经典算法. 比如回溯, 动态规划, 贪心算法, 分治策略 ... 作为对...
订单分批matlab代码不成对的GANCS 当该对(x,y)无法用于训练时,此代码实现了从欠采样测量y中恢复图像x的功能。 但是,我们有少量来自y的地面真相x。 这对于通常无法访问所有器官的高分辨率数据的医学成像应用而言...
用于预处理,读取行为文件,进行第一级和第二级分析的示例管道 该文件夹包含: Powerpoint summary of pipeline used (Example_SPM_Pipeline) Matlab Scripts SPM Batch Files 脚本的组织方式使所有内容都从“ ...
本包装线研发的关键在于利用"转盘式药卷装药机"有序单个抛卷的特点,通过一个简单整理装置将大量连续的药卷进行分堆、并有序地输送至堆码装置;采用高效、精准单支计量技术进行药卷堆码,分隔的药堆与封包膜随动热合、...
为有效利用这一粘土资源,剥离层采用"分质分采、分级分堆、搭配使用"方法,使粘土利用率达到83%。工程采用"总体控制采样"和"具体工作面抽样采样"以指导剥离粘土的开采和堆放。同时对堆场粘土进行定期抽样分析。精密...
本程序采用人机交互模式,由己方先走(人),然后电脑利用博弈树的思想,根据极大极小的递归搜索算法搜索所有的分堆方案,然后选择最佳走法。
人工智能中博弈树对于分钱币问题的实现 问题描述: 有一定数量的钱币 两个人轮流分 但不能分成两个数量相等的堆 当轮到某一个人时 如果他无法再分堆 则他输
神华新疆某露天煤矿非主采的薄煤层区域,采用传统的爆破技术方案,难以实现该区域...针对此问题,根据煤岩分离基本原理,提出了主要采用数码电子雷管和爆破设计软件实现煤岩同爆技术的爆破方案,取得了较好的煤岩分堆效果。
推土机运土回填可采取分堆集中一次运送方法分段距离约为10 15m以减少运土漏失量 c.土方推至填方部位时应提起一次铲刀成堆卸土并向前行驶0.5 1m 利用推土机后退时将土刮平 d.利用推土机来回行驶进行碾压履带应重叠...