STL源码剖析之序列式容器Heap及Priority Queue
时间：2011-06-11 来源：Aga.J
50 heap
Heap的背景是建立在优先队列的基础上，priority queue允许我们任意的插入一个元素，但是会自动将元素进行排序，使得取出时一定是从优先级最高的元素开始取。我们可以考虑使用list这种数据结构完成priority queue，也就是说，我们可以轻松的完成插入（因为list其实是线性链表），但是我们要取得list中的极值时，则需要对整个list进行遍历。或者我们可以这样考虑，将元素插到list的合适位置，这样一来，虽然很容易取得极值，但是我们的搜索插入也是需要线性搜索。
很自然的想到二分法来减少复杂度，也就是使用二叉搜索树，这样插入和求极值都值需要O（logN）的复杂度，但是这要求二叉搜索树的输入元素要随机，不能按照有序的输入，而且二叉搜索树不容易实现，所以我们选择binary heap来构造这样的容器【方便进行插入，检索，排序】
Binary heap其实就是一棵完全二叉树，我们知道完全二叉树可以使用普通的array来实现，因为节点i的左子节点就在2i处，右子节点在2i+1处，而父节点则在i/2处，这种表述法称为隐式表述法，考虑到array无法动态改变大小，我们使用之前定义的vector来实现我们的heap
51 heap的基本操作
Push_heap:
将元素插入到vector尾部，再对元素进行“上溯”，也就是和父节点比较，如果大于父节点，则交换位置，直到不大于或者没有父节点位置
Template<calss RandomAccessIterator>
Inline void upSortLastElem( RandomAccessIterator first, RandomAccessIterator last)
{ // } Template<class RandomAccessIterator> Inline void push_heap( RandomAccessIterator first; RandomAccessIterator last) 参数的用意：first用来作为堆的起始位置标识，last作为最后元素的位置，执行上移 然后借助traits来获得类型的distance_type定义，value_type定义 { __push_heap_aux( first, last, distance_type(first), value_type(first) ); // distance_type(first) //得到first迭代器的distance_type指针对象 // value_type(first) // 得到first迭代器的value_type的指针对象 // 这两个操作主要是为了要求的迭代器的类型信息！！也就是前面定义类型信息的作用，使用traits技巧“萃取”。 } Template<class RandomAccessIterator , class Distance, class T> Inline void __push_heap_aux( RandomAccessIterator first, RandomAccessIterator last, Distance* , T*) //得到Distance和T的类型信息
{ __push_heap( first, Distance( (last-first)-1), distance(0), T(*(last-1))); 这样一来就可以轻松的求得distance了。 化为求last到first的distance，和last-1的T类型 } Template<class RandomAccessIterator, class Distance,class T> Void __push_heap(RandomAccessIterator first, Distance holeIndex, Distance topIndex, T value) { //前面传入的参数holeIndex = Distance( (last-first) -1 ); Distance parent = (holeIndex-1)/2; //求得被插入的节点的父亲的distance While( holeIndex>topIndex && *(first+parent)<value) //如果当前值大于父亲并且不到顶部节点 { *(first+holeIndex) = *(first+parent); holeIndex= parent; parent = (holeIndex-1)/2; } *(first + holeIndex)=value; //交换回来 } 在while中的holeIndex>topIndex是必须要考虑的！处理数组的所有操作时都要考虑到边界的问题。 52 弹出最大元素的过程是先将最大元素（vector首位）与最小元素（vector尾部）进行交换，然后再将当前最顶元素进行“下溯”操作，移动到正确的位置上，减少heap的长度。 Template<class RandomAccessIterator> Inline void pop_heap ( RandomAccessIterator first, RandomAccessIterator last) { //只需要指明进行堆pop操作的起始位置和终止位置，就可以完成弹出first位置的元素 //并调节堆实现堆原有的属性 __pop_heap_aux(first,last,value_type(first)); 这里value_type使用traits技巧，取得迭代器内的实际值 } Template<class RandomAccessIterator, class T> Inline void __pop_heap_aux( RandomAccessIterator first, RandomAccessIterator first, T*) { //pop_element_value = T(*(last-1)); //使用traits获得最后节点类型 //再次使用traits得到distance type __pop_heap( first, last-1,last-1, T(*(last-1)),distance_type(first) ); // [first , last-1) } //重整[first , last-1) Template<class RandomAccessIterator, class T, class Distance> Inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator result, T value, Distance* ) { *result = *first; 参数value就是最后一个数的值 这条语句把第一个数的值存到最后一个上，而最后一个元素值已经存放在value里面 __adjust_heap(first, Distance(0), Distance(last-first),value); //下溯 } Template<class RandomAccessIterator, calss Distance, class T> Void __adjust_heap(RandomAccessIterator first, Distance holeIndex, Distance len, T value) { //直接从孩子节点中选取一个节点来替换hole，然后再让这个节点为hole Distance topIndex=holeIndex; //待下滑的节点 Distance secondChild= 2*topIndex+2; //右孩子 While ( secondChild < len) //注意，堆的左右是没有大小之分的，不是BST { /* //错误，不是BST If( value<*(first+secondChild-1) ) { *(first+topIndex)=*(first+secondChild-1); topIndex=secondChild -1; } Else if (value > *(first+secondChild)) { *(first+topIndex)=*(first+secondChild); topIndex=secondChild; } */ If ( *(first+secondChild) < *(first + (secondChild-1))) --secondChild; *(first+holeIndex) = *(first+secondChild); holeIndex=secondIndex; //迭代 secondChild = 2*secondChild +2; } If ( secondChild == len) //虽然能得到secondChild==len，其实这个位置是没有元素的 { (*first + holeIndex) = *(first + secondChild-1); holeIndex= secondChild-1; } //到达树的尾部 *(first+holeIndex)=value; //原来最后的那个拟定和顶部元素交换的元素赋值回去最后的hole } 53 sort heap 堆排序 算法 Template< class RandomAccessIterator> Void sort_heap(RandomAccessIterator first, RandomAccessIterator last) { While ( last > first) //while 判断的边界 //堆排序只需要不断的进行pop，就可以得到有序堆 { Pop_heap(first, last); //不断调用pop_heap来达到效果，因为pop过程中并不是把元素删了，而是把最大的移到最后 Last--; } } 54 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-2)/2; //只能对树的内部节点进行“下溯” While(true) { __adjust_heap( first, parent, len,T(*(first+parent))); If(parent==0) return; --parent; } } } 测试： #include<vector> #include<iostream> #include<algorithm> //heap 的算法 Using namespace std; Int main() { Int ia[9] = {0,1,2,3,4,8,9,3,5}; Vector<int> ivec(ia,ia+9); Make_heap(ivec.begin(), ivec.end()); //使用堆算法，使得Vector<int> ivec有了堆的特性 For(int i=0;i<ivec.size();i++) { Cout<<ivec[i]<<’ ‘; } Cout<<endl; Ivec.push_back(7); Push_heap(ivec.begin(),ivec.end()); //插入新元素后需要维持原有的堆性质 For(int i=0;i<ivec.size();++i) Cout<<ivec[i]<<’ ‘; Cout<<endl; Pop_heap(ivec.begin(),ivec.end()); Cout<<ivec.back()<<endl; Ivec.pop_back(); For(int i=0;i<ivec.size();++i) Cout<<ivec[i]<<’ ‘; Cout<<endl; Sort_heap(ivec.begin(),ivec.end()); //…. } //堆底层可以依靠vector或者array来实现，同时他使用一些堆算法来完成堆本身的操作，这些堆算法可以被用在其他容器上，有很大的价值。 53 Priority Queue Priority queue在元素的基本操作上和queue一致，但是其中的元素并非按照插入到的顺序排列的，而是自动按照元素的权值排列的 缺省情况下，priority queue是使用一个max-heap完成的,所以priority queue也是依赖于vector的。 Template<class T, class Sequence=vector<T> , class Compare= less<typename Sequence::value_type> Class priority_queue { Public: Typedef typename Squence::value_type value_type; Typedef typename Sequence::size_type size_type; Typedef typename Sequence::reference reference; Typedef typename Sequence::const_reference const_reference; Protected: Sequence c; 因为heap并没有明确的类型定义 对heap的使用都是通过vector<T> 加上 heap算法来实现 Compare comp; Public: Priority_queue(): c(){} Explict priority_queue ( const compare& x): c().comp(x){} Template<class InputIterator> Priority_queue(InputIterator first, InputIterator last, const Compare& x) //在构造函数里面执行构建max heap的操作，使得传入的vector在priority queue里面的顺序是max heap得到的顺序 : c(first,last), comp(x){make_heap(c.begin(), c.end(),comp );} Template<class InputIterator> Priority_queue(InputIterator first, InputIterator last) : c(first, last) { make_heap(c.begin(),c.end(),cmp);} Bool empty() const{ return c.empty();} Size_type size() const {return c.size();} Const_reference top() const{return c.front();} Void push( const value_type& x) { __STL_TRY { c.push_back(x); //底层的vector数据结构加上上层的heap操作 push_heap ( c.begin(), c.end(), comp); } __STL_UNWIND(c.clear()); } Void pop() { __STL_TRY { pop_heap(c.begin,c.end(),comp); c.pop_back(); } __STL_UNWIND( c.clear() ); } }; 类的测试代码 #include<queue> //Priority_queue #include<iostream> #include<algorithm> Using namespace std; Int main() { Int ia[9] ={0,1,2,3,4,8,9,3,5}; Priority_queue<int> ipq(ia,ia+9); 普通的指针也可以做iterator，因为priority queue的底层是vector，而vector因为是array base，所以可以使用普通的指针作为iterator Cout<<”size=”<<ipq.size()<<endl; For( int i=0, i< ipq.size();++i) Cour<<ipq.top()<<” “; //取得优先队列的第一个数，不弹出，所以都一样 Cout<<endl; While(!ipq.empty()) { Cout<<ipq.top()<’’; Ipq.pop(); } Cout<<endl; } /* priority_queue的类原型 template<class T, class Sequence=vector<T>,class Iterator> class priority_queue { public: typedef typename Sequence::value_type value_type; //T typedef typename Sequence::size_type size_type; //size_t typedef typename Sequence::reference reference; //T& typedef typename Sequence::pointer pointer; //T* protected: Sequence seq; public: priority_queue():seq(){} priority_queue(const Sequence& s):seq(s){} priority_queue(Iterator first, Iterator last):seq(first,last){make_heap(first,last);} const_reference top(){return seq.top();} //const_reference void pop(){ seq.pop_front(); pop_heap(first,last);} void push() {seq.push_back(x); push_back(first,last); } }; */
{ // } Template<class RandomAccessIterator> Inline void push_heap( RandomAccessIterator first; RandomAccessIterator last) 参数的用意：first用来作为堆的起始位置标识，last作为最后元素的位置，执行上移 然后借助traits来获得类型的distance_type定义，value_type定义 { __push_heap_aux( first, last, distance_type(first), value_type(first) ); // distance_type(first) //得到first迭代器的distance_type指针对象 // value_type(first) // 得到first迭代器的value_type的指针对象 // 这两个操作主要是为了要求的迭代器的类型信息！！也就是前面定义类型信息的作用，使用traits技巧“萃取”。 } Template<class RandomAccessIterator , class Distance, class T> Inline void __push_heap_aux( RandomAccessIterator first, RandomAccessIterator last, Distance* , T*) //得到Distance和T的类型信息
{ __push_heap( first, Distance( (last-first)-1), distance(0), T(*(last-1))); 这样一来就可以轻松的求得distance了。 化为求last到first的distance，和last-1的T类型 } Template<class RandomAccessIterator, class Distance,class T> Void __push_heap(RandomAccessIterator first, Distance holeIndex, Distance topIndex, T value) { //前面传入的参数holeIndex = Distance( (last-first) -1 ); Distance parent = (holeIndex-1)/2; //求得被插入的节点的父亲的distance While( holeIndex>topIndex && *(first+parent)<value) //如果当前值大于父亲并且不到顶部节点 { *(first+holeIndex) = *(first+parent); holeIndex= parent; parent = (holeIndex-1)/2; } *(first + holeIndex)=value; //交换回来 } 在while中的holeIndex>topIndex是必须要考虑的！处理数组的所有操作时都要考虑到边界的问题。 52 弹出最大元素的过程是先将最大元素（vector首位）与最小元素（vector尾部）进行交换，然后再将当前最顶元素进行“下溯”操作，移动到正确的位置上，减少heap的长度。 Template<class RandomAccessIterator> Inline void pop_heap ( RandomAccessIterator first, RandomAccessIterator last) { //只需要指明进行堆pop操作的起始位置和终止位置，就可以完成弹出first位置的元素 //并调节堆实现堆原有的属性 __pop_heap_aux(first,last,value_type(first)); 这里value_type使用traits技巧，取得迭代器内的实际值 } Template<class RandomAccessIterator, class T> Inline void __pop_heap_aux( RandomAccessIterator first, RandomAccessIterator first, T*) { //pop_element_value = T(*(last-1)); //使用traits获得最后节点类型 //再次使用traits得到distance type __pop_heap( first, last-1,last-1, T(*(last-1)),distance_type(first) ); // [first , last-1) } //重整[first , last-1) Template<class RandomAccessIterator, class T, class Distance> Inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator result, T value, Distance* ) { *result = *first; 参数value就是最后一个数的值 这条语句把第一个数的值存到最后一个上，而最后一个元素值已经存放在value里面 __adjust_heap(first, Distance(0), Distance(last-first),value); //下溯 } Template<class RandomAccessIterator, calss Distance, class T> Void __adjust_heap(RandomAccessIterator first, Distance holeIndex, Distance len, T value) { //直接从孩子节点中选取一个节点来替换hole，然后再让这个节点为hole Distance topIndex=holeIndex; //待下滑的节点 Distance secondChild= 2*topIndex+2; //右孩子 While ( secondChild < len) //注意，堆的左右是没有大小之分的，不是BST { /* //错误，不是BST If( value<*(first+secondChild-1) ) { *(first+topIndex)=*(first+secondChild-1); topIndex=secondChild -1; } Else if (value > *(first+secondChild)) { *(first+topIndex)=*(first+secondChild); topIndex=secondChild; } */ If ( *(first+secondChild) < *(first + (secondChild-1))) --secondChild; *(first+holeIndex) = *(first+secondChild); holeIndex=secondIndex; //迭代 secondChild = 2*secondChild +2; } If ( secondChild == len) //虽然能得到secondChild==len，其实这个位置是没有元素的 { (*first + holeIndex) = *(first + secondChild-1); holeIndex= secondChild-1; } //到达树的尾部 *(first+holeIndex)=value; //原来最后的那个拟定和顶部元素交换的元素赋值回去最后的hole } 53 sort heap 堆排序 算法 Template< class RandomAccessIterator> Void sort_heap(RandomAccessIterator first, RandomAccessIterator last) { While ( last > first) //while 判断的边界 //堆排序只需要不断的进行pop，就可以得到有序堆 { Pop_heap(first, last); //不断调用pop_heap来达到效果，因为pop过程中并不是把元素删了，而是把最大的移到最后 Last--; } } 54 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-2)/2; //只能对树的内部节点进行“下溯” While(true) { __adjust_heap( first, parent, len,T(*(first+parent))); If(parent==0) return; --parent; } } } 测试： #include<vector> #include<iostream> #include<algorithm> //heap 的算法 Using namespace std; Int main() { Int ia[9] = {0,1,2,3,4,8,9,3,5}; Vector<int> ivec(ia,ia+9); Make_heap(ivec.begin(), ivec.end()); //使用堆算法，使得Vector<int> ivec有了堆的特性 For(int i=0;i<ivec.size();i++) { Cout<<ivec[i]<<’ ‘; } Cout<<endl; Ivec.push_back(7); Push_heap(ivec.begin(),ivec.end()); //插入新元素后需要维持原有的堆性质 For(int i=0;i<ivec.size();++i) Cout<<ivec[i]<<’ ‘; Cout<<endl; Pop_heap(ivec.begin(),ivec.end()); Cout<<ivec.back()<<endl; Ivec.pop_back(); For(int i=0;i<ivec.size();++i) Cout<<ivec[i]<<’ ‘; Cout<<endl; Sort_heap(ivec.begin(),ivec.end()); //…. } //堆底层可以依靠vector或者array来实现，同时他使用一些堆算法来完成堆本身的操作，这些堆算法可以被用在其他容器上，有很大的价值。 53 Priority Queue Priority queue在元素的基本操作上和queue一致，但是其中的元素并非按照插入到的顺序排列的，而是自动按照元素的权值排列的 缺省情况下，priority queue是使用一个max-heap完成的,所以priority queue也是依赖于vector的。 Template<class T, class Sequence=vector<T> , class Compare= less<typename Sequence::value_type> Class priority_queue { Public: Typedef typename Squence::value_type value_type; Typedef typename Sequence::size_type size_type; Typedef typename Sequence::reference reference; Typedef typename Sequence::const_reference const_reference; Protected: Sequence c; 因为heap并没有明确的类型定义 对heap的使用都是通过vector<T> 加上 heap算法来实现 Compare comp; Public: Priority_queue(): c(){} Explict priority_queue ( const compare& x): c().comp(x){} Template<class InputIterator> Priority_queue(InputIterator first, InputIterator last, const Compare& x) //在构造函数里面执行构建max heap的操作，使得传入的vector在priority queue里面的顺序是max heap得到的顺序 : c(first,last), comp(x){make_heap(c.begin(), c.end(),comp );} Template<class InputIterator> Priority_queue(InputIterator first, InputIterator last) : c(first, last) { make_heap(c.begin(),c.end(),cmp);} Bool empty() const{ return c.empty();} Size_type size() const {return c.size();} Const_reference top() const{return c.front();} Void push( const value_type& x) { __STL_TRY { c.push_back(x); //底层的vector数据结构加上上层的heap操作 push_heap ( c.begin(), c.end(), comp); } __STL_UNWIND(c.clear()); } Void pop() { __STL_TRY { pop_heap(c.begin,c.end(),comp); c.pop_back(); } __STL_UNWIND( c.clear() ); } }; 类的测试代码 #include<queue> //Priority_queue #include<iostream> #include<algorithm> Using namespace std; Int main() { Int ia[9] ={0,1,2,3,4,8,9,3,5}; Priority_queue<int> ipq(ia,ia+9); 普通的指针也可以做iterator，因为priority queue的底层是vector，而vector因为是array base，所以可以使用普通的指针作为iterator Cout<<”size=”<<ipq.size()<<endl; For( int i=0, i< ipq.size();++i) Cour<<ipq.top()<<” “; //取得优先队列的第一个数，不弹出，所以都一样 Cout<<endl; While(!ipq.empty()) { Cout<<ipq.top()<’’; Ipq.pop(); } Cout<<endl; } /* priority_queue的类原型 template<class T, class Sequence=vector<T>,class Iterator> class priority_queue { public: typedef typename Sequence::value_type value_type; //T typedef typename Sequence::size_type size_type; //size_t typedef typename Sequence::reference reference; //T& typedef typename Sequence::pointer pointer; //T* protected: Sequence seq; public: priority_queue():seq(){} priority_queue(const Sequence& s):seq(s){} priority_queue(Iterator first, Iterator last):seq(first,last){make_heap(first,last);} const_reference top(){return seq.top();} //const_reference void pop(){ seq.pop_front(); pop_heap(first,last);} void push() {seq.push_back(x); push_back(first,last); } }; */
相关阅读 更多 +
排行榜 更多 +
