} } }

    数据布局练手05 关于堆的up策略和down策略实现

    添加时间:2013-5-28 点击量:

    堆,是一个相当首要的数据布局,它是优先队列,堆排序,Dijkstra等算法的实现包管!


    堆的首要特点是:


    1、根结点是最大/小,而这个首要的差别,就是实现斗劲操纵时是less or greater, 是以可以应用纯虚化 斗劲接口,把实现放到子类。 附: STL中采取的是模板默认参数的办法实现。


    2、须要两个默示大小的变量来标定堆or数组的大小。因为pop操纵因让堆的有效长度变小,而数组的长度不变。


    3、堆的插入操纵一般是插入到数组的末尾,这里好用vector, 因为它可以在常数时候内尾插入数据且可以或许动态发展。




     1 #include <vector>
    
    2 #include <ostream>
    3 using namespace std;
    4 template<class T>
    5 class HEAP{
    6 protected:
    7 vector<T> elements;
    8 int totalSize;
    9 public:
    10 HEAP() : totalSize(0),elements(){}
    11 virtual ~HEAP(){}
    12 int left(int index){return 2index+1;}
    13 int right(int index){return 2index+2;}
    14 int parent(int index){return (index-1)/2;}
    15
    16 void upHeapity(int index);
    17 void downheapity(int index);
    18
    19 void makeHeap_up();
    20 void makeHeap_down();
    21
    22 T& pop_up();
    23 T& pop_down();
    24
    25 void _up(const T& x);
    26 void _down(const T& x);
    27 void swap(T& a, T& b){int tmp=a; a=b; b=tmp;}
    28 void show(ostream& os) const;
    29 void sort();
    30
    31 virtual bool comp(int a, int b)=0;
    32 };


    类定义



     1 template<class T>
    
    2 class maxHeap : public HEAP<T>{
    3 public:
    4 maxHeap() : HEAP<T>(){}
    5 ~maxHeap(){};
    6 bool comp(int a, int b) { return elements[a]>elements[b]? true:false;}
    7 };
    8
    9 template<class T>
    10 class minHeap : public HEAP<T>{
    11 public:
    12 minHeap() : HEAP<T>(){}
    13 ~minHeap(){};
    14 bool comp(int a, int b) { return elements[a]<elements[b]? true: false;}
    15 };


    子类定义

    要包管这个heapity特点,(假定是评论辩论最大堆)一般有两种体式格式:从根到叶(down) 和 从叶到根(up),这两种实现各有优毛病。我们先说下各类操纵的文字表述:


    <<算法导论>>中采取了down的策略,即斗劲本结点,阁下结点,获得最大值的下标索引,若不是最大索引不是本结点,则互换本结点和最大索引,接着用最大索引实现递归操纵。downHeapity包管了该子树满足堆的特点。




     1 template<class T>
    
    2 void HEAP<T>::downheapity(int index)
    3 {
    4 int l = left (index);
    5 int r = right(index);
    6 int large = index;
    7 if(l<totalSize)
    8 if(comp(l,index))
    9 large = l;
    10 else
    11 large = index;
    12 if(r<totalSize)
    13 if(comp(r,large))
    14 large = r;
    15 if(index != large){
    16 swap(elements[index], elements[large]);
    17 downheapity(large);
    18 }
    19 }


    downheapity策略

    StL中采取了是up的策略,即新增长结点时,仅需层层斗劲和父节点的大小,最多到根节点。up策略满足了从该叶到根的路径满足了堆的特点




    1 template<typename T>
    
    2 void HEAP<T>::upHeapity(int index)
    3 {
    4 while((index!=0) && (comp(index, parent(index)))){
    5 swap(elements[index], elements[parent(index)]);
    6 index = parent(index);
    7 }
    8 }


    upheapity策略



    别的,在建堆操纵中,若采取down策略,则可以从index= lenArray/2 的地位进行downHeapity(index)一向递减到根结点就行。




    1 template<class T>
    
    2 void HEAP<T>::makeHeap_down()
    3 {
    4 totalSize = elements.size(); // 很首要,从头调剂堆大小
    5 forint i=totalSize>>1; i>=0; --i){ // 从一半到零
    6 downheapity(i);
    7 }
    8 }


    建堆的down策略

    而采取up策略,则从index = lenArray-1的地位递减到 lenArray/2的地位,中心一向调用upHeapity(index)就行。




    1 template<class T>
    
    2 void HEAP<T>::makeHeap_up()
    3 {
    4 totalSize = elements.size();
    5 forint i=elements.size()-1; i>elements.size()/2; --i) {
    6 upHeapity(i);
    7 }
    8 }


    建堆的up策略



    我们对堆进行pop操纵时,一般来说要保存根结点的值用于最后的返回。实现中我们还须要将根结点和尾结点的值进行互换。这里持续说下down策略和up策略的做法。


    down策略时,因为前一步已经互换了根结点和尾结点,且调剂了堆大小的长度,如许,我们就可以从索引为堆大小一半的地位开端,递减到根,一向调用 downheapity(index)就行。




     1 template<class T>
    
    2 T& HEAP<T>::pop_down()
    3 {
    4 T rval = elements[0];
    5 swap(elements[0],elements[totalSize-1]);
    6 totalSize--;
    7 forint i=totalSize/2; i>=0; i--){
    8 downheapity(i);
    9 }
    10 return rval;
    11 }


    pop操纵的down策略

    up策略是,就斗劲麻烦点了,须要将互换后的根结点下放到某个小值的地位,然后再调用次upheapity包管堆特点的满足。这个实现起来斗劲憎恶,要断定一些鸿沟前提。




     1 template<class T>
    
    2 T& HEAP<T>::pop_up()
    3 {
    4 T rval = elements[0];
    5 swap(elements[0],elements[totalSize-1]);
    6 totalSize--;
    7 int i=0;
    8 int tmp=i;
    9 while(left(i)<totalSize){
    10 if( (right(i)<totalSize) && comp(left(i),right(i)) || (right(i)>=totalSize)){
    11 tmp = left(i);
    12 }
    13 if( (right(i)<totalSize) && (!comp(left(i),right(i)))){
    14 tmp = right(i);
    15 }
    16 swap(elements[i],elements[tmp]);
    17 i = tmp;
    18 }
    19 upHeapity(tmp);
    20 return rval;
    21 }


    pop操纵的up策略



    而对于堆排序,则就是遍历调用pop n-1次就行。




    1 template<class T>
    
    2 void HEAP<T>::sort()
    3 {
    4 int t = totalSize;
    5 forint i=0; i<t; ++i){
    6 pop_up();
    7 // pop_down();
    8 }
    9 }


    堆排序



    对于元素的插入来说,那必然是StL的up占优了。因为up策略就是从尾结点开端向父节点进行斗劲,最多斗劲到根节点。 而若采取down策略,则从堆大小一半的地位递减到根,此中一向调用downheapity(index)操纵。




     1 template<typename T>
    
    2 void HEAP<T>::_up(const T& x)
    3 {
    4 if(totalSize == elements.size())
    5 elements.push_back(x);
    6 else
    7 elements[totalSize] = x;
    8 totalSize++;
    9 upHeapity(totalSize-1);
    10 }
    11
    12 template<typename T>
    13 void HEAP<T>::_down(const T& x)
    14 {
    15 if(totalSize == elements.size())
    16 elements.push_back(x);
    17 else
    18 elements[totalSize] = x;
    19 totalSize++;
    20 forint i=totalSize/2; i>=0; i--){
    21 downheapity (i);
    22 }
    23 }


    的down策略和up策略



    是以,这里我们可以总结下应用堆时辰的策略:


    除了插入操纵应用up策略外,其他所有的操纵都应用down策略。调用down策略,都从一半堆大小的地位开端递减到根。


    别的,对于鸿沟前提来说,down策略一般从尾结点的父节点开端,及 parent(totalSize-1), 即 (totalSize-1)/2; 因为下标从0开端,鸿沟前提就很让人纠结,我们宁肯多操纵一次,及从total/2地位开端,如许也没啥影响。



    • 之前我的总结有题目,今天反思了下,若都从一半堆大小开端递减到根,那么时候错杂度挺大的。其实所有的操纵都采取down策略更易懂得。

    • 对于从(size-1)/2还是size/2开端,我感觉还是从(size-1)/2更好,如许轮回代码可以批改下,且也能避免上方所误会的处所



     1     _down 和 pop_down 中的
    /for(int i=totalSize/2; i>=0; i--){
    2 downheapity(i);
    3 }/
    4 改为:
    5 int p = parent (totalSize-1);
    6 while( p != parent(p)){
    7 downheapity (p);
    8 p = parent(p);
    9 }
    10 downheapity(p);



    应用堆的时辰,必然要重视是采取数组长度还是堆长度。我们可以总结下:仅建堆时采取数组长度,同时堆长度便是数组长度其余操纵应用的都是堆长度,同时要重视调剂堆长度水位


    测试代码:




     1 #include myHeap.h
    
    2 #include <iostream>
    3 using namespace std;
    4
    5 int main()
    6 {
    7 maxHeap<int> mh;
    8 mh._down(170);
    9 mh._down(20);
    10 mh._down(30);
    11 mh._down(1);
    12 mh._down(7);
    13
    14 mh._down(10);
    15 mh._down(90);
    16
    17 cout << mh << endl;
    18 cout << -------- << endl;
    19 mh.sort();
    20 cout << mh << endl;
    21 mh.makeHeap_up();
    22 cout << mh << endl;
    23 }


    测试代码

    真正的心灵世界会告诉你根本看不见的东西,这东西需要你付出思想和灵魂的劳动去获取,然后它会照亮你的生命,永远照亮你的生命。——王安忆《小说家的十三堂课》
    分享到: