- heap可分为max-heap以及min-heap而在此文中所要介紹的是max-heap,所谓max-heap即每个节点的键值都大于或等于其子节点键值,其最大值在根节点总是位于底层array或vector的首部
- 首先了解priorityqueue queue,允许用户以任何次序将任何元素推入容器内但取出时一定是从优先权最高的元素开始取
- 下面我们来分析一下为何采用heap:
- 采用list:当元素插入操作达到常数时間,但取值却需要对整个list进行扫描;将list先排序使得list由大到小,这样取值与删除可达到最高效率但元素插入却只有线性表现,不能两者兼得
- 结合上述又能满足priorityqueue queue的条件,又能达到高效率binary heap就这样作为了其底层实现
complete binary tree 整棵树内没有任何节点漏洞,这带来一个极大的好处:我们鈳以利用array来存储所有节点假设动用一个小技巧,将array的#0元素保留(或设为无限大或无限小)那么当complete binary tree中的某个节点位于array的i处时,其左子节點必位于array的2i处其右子节点比位于array的2i+1处,其父节点必位于“i/2”处通过这么简单的位置规则,array可以轻易实现出complete binary tree这种以array表述tree的方式,我们稱为隐式表述法
这么一来,我们需要的工具就很简单了:一个array 和 一组 heap算法(用来进行元素操作并将某一整组数据排列成一个heap)。array的缺點是无法动态改变大小而heap却需要这项功能,因此以vector代替array是更好的选择。
为了满足complete binary tree的条件新加入的元素一定要放在最下一层作为叶节點,并填补在由左至右的第一个空格也就是把新元素插入在顶层vector的end()处
-
percolate up(上溯)程序:将新节点拿来与其父节点比较,如果其键值比父节點大就父子对换位置,如此一直上溯直到不需要对换或直到根节点为止
-
当push_heap被调用时,新元素应已置于底部容器的最尾端
- percolate_down(下溯)程序:将空间节点和其较大子节点“对调”并持续下放直至叶节点为止,然后将前述被割舍的元素值设给空洞节点然后再执行一次“上溯”程序
- 在pop_heap时,除了将最大元素取出之外还需调用__adjust_heap进行堆调整
- 当调用完pop_heap时,最大元素只是被放置于底部容器的最尾端尚未被取走,若要取其值,则需调用back()若要删除,则需调用pop_back()
- 这个算法用来将一段现有数据转换为一个heap