push_heap算法 （即满足max-heap条件，最大值在根节点）

算法描述

完全二叉树，父节点值比子节点大。（不保证左节点值大于右节点值。）

 

新元素插入时要满足的条件

为了满足完全二叉树的条件，新加入的元素一定要放在最下一层作为叶节点，并填补在由左至右的第一个空格，也就是把新元素插入在底层vector的end()处。

 

用到的技巧

这里有一个小技巧，如果用array存储所有节点，并且将array的#0位置的元素保留（即下标从1开始），那么当完全二叉树的某个节点位移array的i处时，其左节点必位于array的2i处，其右节点必位于array的2i+1处，其父节点必位于”i/2”处（i/2取整）。用array实现完全二叉树的方式称为隐式表述法（implicit representation）。

 

SGI  STL  push_heap算法实现

SGI STL计算父节点与左右节点的方式与上面的技巧略有不同，但原理类似（可以认为SGI中下标从1开始）。

算法核心：

// 以下這組 push_back()不允許指定「大小比較標準」 template <class RandomAccessIterator, class Distance, class T> void __push_heap(RandomAccessIterator first, Distance holeIndex,Distance topIndex, T value) {Distance parent = (holeIndex - 1) / 2; // 找出父節點while (holeIndex > topIndex && *(first + parent) < value) {// 當尚未到達頂端，且父節點小於新值（於是不符合 heap 的次序特性）// 由於以上使用 operator<，可知 STL heap 是一種 max-heap（大者為父）。*(first + holeIndex) = *(first + parent); // 令洞值為父值holeIndex = parent; // percolate up：調整洞號，向上提昇至父節點。parent = (holeIndex - 1) / 2; // 新洞的父節點} // 持續至頂端，或滿足 heap 的次序特性為止。*(first + holeIndex) = value; // 令洞值為新值，完成安插動作。 }

 

 接口函数： template <class RandomAccessIterator, class Compare> inline void push_heap(RandomAccessIterator first, RandomAccessIterator last,Compare comp) {__push_heap_aux(first, last, comp, distance_type(first), value_type(first)); } template <class RandomAccessIterator, class Compare, class Distance, class T> inline void __push_heap_aux(RandomAccessIterator first,RandomAccessIterator last, Compare comp,Distance*, T*) {__push_heap(first, Distance((last - first) - 1), Distance(0), T(*(last - 1)), comp); }

转载于:https://www.cnblogs.com/helloweworld/archive/2013/01/05/2845528.html

总结

以上是生活随笔为你收集整理的push_heap算法 （即满足max-heap条件，最大值在根节点）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。