首页 > 代码库 > STL_堆

STL_堆

STL中priority_queue优先队列采用堆数据结构实现。堆算法具有nlog(n)的算法时间复杂度,底层采用vector实现堆的数据机构。默认为根节点大于左右子树值即最大堆。

1、元素入堆:push_heap(first,last [,comp])

辅助函数:push_heap(first,holeIndex,topIndex,value)

//first为堆顶迭代器。holeindex为当前要插入的位置,topindex为堆顶的索引值,这些都为vector中的索引值即数值。value为holeIndex处的值,依照队的大小关系,可将其上调到topIndex元素位置下面甚至topIndex位置处。

首先找寻到holeIndex的父节点索引,当其父节点未达到根节点且父节点小于当前节点值时,赋予父节点当前的value值,继续上溯。

技术分享

push_heap_aux(first,last,distance ,T*)调用push_heap(first,holeIndex,topIndex,value),push_heap(first,last)调用push_heap_aux()

 

2、创建堆 make_heap(first,last)

其中最主要的是一个辅助调整函数adjust_heap(),该函数调整节点与其左右子节点的大小,使得根节点放子树节点中较大的数值,再从底往上依次入堆的调整。

技术分享

在make_heap中,从最后一个元素的父节点开始,依次借助上述辅助函数往上调整,直至根节点。

3、元素出堆:pop_heap()弹出堆顶元素

此部分需要借助前面函数,将堆顶元素与最后元素交换,在调用adjust_heap函数将根节点下调,直至新的最后节点(原来的倒数第二个节点):adjust_heap(first,distance(0),distance(last-first),value)

4、堆排序:sort_heap(first,last) 时间:O(nlgn)

内部一个while循环逐层将完全二叉树的最大元素移动到最后,最终形成一个有序的次序:

while(last-first>1)

  pop_heap(first,last--);

5、是否为堆is_heap(first,last)

用一个for循环从根节点0索引值开始,与从1开始索引的左右子节点进行比较,一旦父节点小于子节点返回false,比较过程中,若子节点为偶数,比为右节点,其根节点加一。

parent = 0;

for(child<1;chile<n;++child)

{

  if (first[parent]<first)   return false;

  if ((child&1)==0)  ++parent;

}

return true;

STL_堆