简述
heap并不属于STL容器组件，它是priority queue的助手。
priority queue允许用户以任何次序将任何元素推入容器中，但取出时一定是从优先权最高的元素开始取。
binary heap是一种完全二叉树，即，整颗二叉树，除了最底层的叶子节点之外，是填满的，而最底层的叶子节点从左至右又不得有空隙。
完全的二叉树没有任何节点漏洞，这样就有个好处：可以利用
array来储存所有节点，假设让array的#0元素保存无限大值或无限小值。那么，当完全二叉树的某个节点位于array的i处时，其左子节点必位于array的2i处，其右子节点比位于array的2i+1处，其父节点必位于i/2处。通过这个规则，
array可以轻易实现完全二叉树。根据元素排列方式，
heap可分为max-heap和min-heap两种，前者的每个节点的键值都大于等于其子节点值，后者的每个节点的键值都小于等于其子节点的键值。因此，max-heap的最大值在根节点，并总是位于底层的array或vector的起头处；min-heap的最小值在根节点，同样总是位于array或vector的起头处。
heap的所有元素都必须遵循特别的二叉树排列规则，所以heap不提供遍历功能，也不提供迭代器。
heap算法
push_heap
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
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*) { __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(holeIndex > topIndex && *（first+parent)<value) { *(first+holeIndex) = *(first+parent); holeIndex = parent; parent = (holeIndex - 1)/2;//新的父节点 } *(first+holeIndex) = value; } |
pop_heap
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
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); } template <class RandomAccessIterator,class Distance,class T> void __adjust_heap(RandomAccessIterator first,Distance holeIndex,Distance len,T value) { Distance topIndex = holeIndex; Distance secondChild = 2*holeIndex + 2; while(secondChild < len) { if(*(first+secondChild) < *(first+(secondChild - 1))) secondChild--; *(first+holeIndex) = *(first+secondChild); holeIndex = secondChild; secondChild = 2 * (secondChild + 1); } if(secondChild == len) { *(first + holeIndex) = *(first+(secondChild - 1)); holeIndex = secondChild - 1; } __push_heap(first,holeIndex,topIndex,value); } |
sort_heap
|
1 2 3 4 5 6 |
template <class RandomAccessIterator> void sort_heap(RandomAccessIterator first,RandomAccessIterator last) { while(last - first > 1) pop_heap(first,last--); } |
make_heap
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
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 - 2) / 2; while(true) { __adjust_heap(first,parent,len,T(*(first+parent))); if(parent == 0) return; parent--; } } |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ C++_volatile10/08
- ♥ Deelx正则引擎使用12/24
- ♥ Effective C++_第五篇07/02
- ♥ 51CTO：C++编程技巧与规范08/01
- ♥ Soui九07/25
- ♥ Soui应用 动画二06/27