①push_heap算法 以下是push_heap算法的实现细节。该函数接收两个迭代器，用来表现一个heap底部容器（vector）的头尾，而且新元素已经插入究竟部的最尾端。 template <class RandomAccessIterator> inline void push_heap(RandomAccessIterator first,RandomAccessIterator last) { //注意，此函数被调用时，新元素应已置于底部容器的最尾端 _push_heap_aux(first,last,distance_type(first),value_type(first)); }
template <class RandomAccessIterator,class Distance,class T> inline void _push_heap_aux(RandomAccessIterator first,RandomAccessIterator last, Distance*,T*) { //以上系依据heap的结构特性：新值必置于底部容器的最尾端，此即第一个洞号：（last-first）-1 _push_heap(first,Distance((last-first)-1),Distance(0),T(*(last-1))); }
template <class RandomAccessIterator,class Distance,class T> void _push_heap(RandomAccessIterator first,Distance holeIndex,Distance topIndex,T value) { Distance parent = (holeIndex-1)/2; while (parent > topIndex && *(first parent)<value) { *(first holeIndex) = *(first parent); holeIndex = parent; parent = (holeIndex-1)/2; } *(first holeIndex) = value; } ②pop_heap算法 pop操作取走根节点（事实上是设至底部容器vector的尾端节点）后，为了满足complete binary tree的条件，必须割舍最下层最右边的叶节点，并将其值又一次安插至最大堆。 template <class RandomAccessIterator> inline void pop_heap(RandomAccessIterator first,RandomAccessIterator last) { _pop_heap_aux(first,last,value_type(first)); }
template <class RandomAccessIterator,class T> inline void _pop_heap_aux(RandomAccessIterator first,RandomAccessIterator last,T*) { _pop_heap(first,last-1,last-1,T(*(last-1)),distance_type(first)); }
template <class RandomAccessIterator,class T,class Distance> inline void _pop_heap(RandomAccessIterator first,RandomAccessIterator last,RandomAccessIterator result, T value,Distance*) { *result = *first; _adjust_heap(first,Distance(0),Distance(last-first),value); //以上欲又一次调整heap，洞号为0（亦即树根处），欲调整值为value（原尾值） }
template <class RandomAccessIterator,class Distance,class T> void _adjust_heap(RandomAccessIterator first,Distance holeIndex,Distance len,T value) { Distance topIndex = holeIndex; Distance secondChild = holeIndex*2 2; while (secondChild < len) { if(*(first secondChild) < *(first secondChild-1)) secondChild–; *(first holeIndex) = *(first secondChild); holeIndex = secondChild; secondChild = holeIndex*2 2; } if (secondChild == len) { *(first holeIndex) = *(first secondChild-1); holeIndex = secondChild-1; } _push_heap(first,holeIndex,topIndex,value); } 注意:pop_heap之后，最大元素仅仅是被置于底部容器的最尾端，尚未被取走。假设要取其值，可使用底部容器（vector）所提供的back()操作函数。假设要移除它，可使用底部容器（vector）所提供的pop_back()操作函数。 ③sort_heap算法 既然每次pop_heap可获得heap中键值最大的元素，假设持续对整个heap做pop_heap操作，每次将操作范围从后向前缩减一个元素（由于pop_heap会把键值最大的元素放在底部容器的最尾端），当整个程序运行完成时，我们便有了一个递增序列。 template<class RandomAccessIterator> void sort_heap(RandomAccessIterator first,RandomAccessIterator last) { while(last – first > 1) pop_heap(first,last–); } ④make_heap算法 这个算法用来将一段现有的数据转化为一个heap。 template <class RandomAccessIterator> inline void make_heap(RandomAccessIterator first,RandomAccessIterator last) { _make_heap(first,last,value_type(first),distance_type(first)); }
template <class RandomAccessIterator,class T,class Distance> void _make_heap(RandomAccessIterator first,RandomAccessIterator last,T*,Distance*) { if (last – first < 2) return; Distance len = last-first; Distance parent = (len-1)/2;
while (true) { _adjust_heap(first,parent,len,T(*(first parent))); if (parent == 0) return; parent–; } }
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/119095.html原文链接：https://javaforall.cn
