• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        


            


            Daly的游戲人生
            

            

            




            
	
					
	
            
		
            
			動態優先隊列
		
            
		    很多圖算法實現中都需要用到優先隊列，這些優先隊列需要能動態改變堆內對應元素的值，并更新堆。比如在dijkstra算法中，每次松弛都要更新頂點的權值，但一般的優先隊列無法找到頂點在堆中的位置。本文實現一種數據結構"動態優先隊列"，利用兩個數組保存了原數據數組位置----堆位置的映射，能實現快速修改。該數據結構的大部分應用場合中，元素個數是固定的，因此代碼中沒有追加新元素的操作。
                 代碼和大部分堆操作一樣，m_indices數組保存了原數組 到 堆位置映射， m_pmap保存了逆向映射。堆調整時，原數組的數據位置不變，只改變m_pmap映射。該實現是最小優先隊列，在模板參數添加用于比較的Functor可改造為任意堆。

            

              1template<typename _Type>
              2static void gs_swap(_Type &x, _Type &y)
              3{    
              4   static _Type tmp;
              5   tmp = x;
              6   x = y;
              7   y = tmp;
              8}
              9
             10
             11/** 
             12* DynamicPQ : dynamic priority queue (with indices mapping to original array position)
             13*   It's a min-heap and has following feature
             14*  1. detemine the min value
             15*  2. modify the corresponding k in original array
             16*  3. pop the top value
             17*  it can't be append new value
             18*/             
             19template<typename _Type>
             20class DynamicPQ
             21{
             22public:
             23     /** 
             24     *  @param  array   the original array to processed
             25     *  @param  max_n   the original size of the array
             26     */
             27    DynamicPQ(_Type *array, unsigned int max_n)
             28        : m_array(array), m_size(max_n)
             29    {
             30        unsigned int i;
             31        m_indices = new unsigned int[max_n];
             32        m_pmap = new unsigned int[max_n];
             33        for (i=0; i<m_size; i++) {
             34            m_indices[i] = m_pmap[i] = i;
             35        }
             36        //make_heap
             37        for (i=m_size/2; i>0; i--) {
             38            adjust_down(i);
             39        }
             40        adjust_down(0);
             41    }
             42
             43    ~DynamicPQ() {
             44        delete[] m_indices;
             45        delete[] m_pmap;
             46    }
             47    /** 
             48    * change the key
             49    * @param k      the original index, not the position of the min-heap
             50    * @param value  new value
             51    */
             52    void modify_key(unsigned int k, _Type value)
             53    {
             54        unsigned int idx = m_indices[k];  //find the coresponding position of the heap
             55        if (value < m_array[ m_pmap[idx] ]) {
             56            m_array[ m_pmap[idx] ] = value;    //decrease key
             57            adjust_up(idx);
             58        }
             59        else {
             60            m_array[ m_pmap[idx] ] = value;    //increase key
             61            adjust_down(idx);
             62        }
             63    }
             64    _Type top() { return m_array[ m_pmap[0] ];}
             65    /** 
             66    * extract the min value
             67    */
             68    _Type pop_top() {
             69        gs_swap(m_pmap[0], m_pmap[m_size-1]);
             70        m_indices[ m_pmap[0] ] = m_size - 1;
             71        m_indices[ m_pmap[m_size-1] ] = 0;
             72        --m_size;
             73        adjust_down(0);    
             74        return m_array[ m_pmap[m_size]];
             75    }
             76    inline unsigned int size() { return m_size; }
             77
             78protected:
             79    //update the value. up to the root
             80    void adjust_up(unsigned int i)
             81    {
             82        unsigned int parent = (i-1) / 2;
             83        while (i>0 && m_array[ m_pmap[i] ] < m_array[ m_pmap[parent] ]) {
             84            gs_swap(m_pmap[i], m_pmap[parent]);
             85            m_indices[ m_pmap[i]] = i;       //update index mapping after exchange
             86            i = parent;
             87            parent = (i-1) / 2;
             88        }
             89        m_indices[ m_pmap[i] ] = i;     //update the final position of i
             90    }
             91    //min-heapify
             92    void adjust_down(unsigned int i)
             93    {
             94        unsigned int lf = i*2 + 1;    //left child
             95        unsigned int rt = i*2 + 2;    //right child
             96        unsigned int min_pos;
             97        unsigned int tmp_i = m_pmap[i];
             98        while(lf < m_size) {            
             99            if (m_array[ m_pmap[lf] ] < m_array[ m_pmap[i] ]) 
            100                min_pos = lf;
            101            else 
            102                min_pos = i;
            103            if (rt < m_size && m_array[ m_pmap[rt] ] < m_array[ m_pmap[min_pos] ]) {
            104                min_pos = rt;
            105            }
            106            if (min_pos != i) {
            107                gs_swap(m_pmap[min_pos], m_pmap[i]);
            108                m_indices[ m_pmap[i]] = i;       //update after exchange
            109                i = min_pos;            //next loop
            110                lf = i*2 + 1;
            111                rt = i*2 + 2;
            112                continue;
            113            }
            114            else {
            115                m_indices[tmp_i] = i;   //update index
            116                break;
            117            }
            118        }
            119    }
            120    
            121protected:
            122    _Type *m_array;       
            123    unsigned int *m_indices;    //index mapping(array[k] --> heap position)
            124    unsigned int *m_pmap;       //pointer mapping(heap position --> array[k])
            125    unsigned int m_size;
            126}            ;
            127
            


            

		
            
			posted on 2009-11-17 11:38 Daly 閱讀(990) 評論(0)  編輯 收藏 引用  所屬分類: 數據結構與算法 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



午夜天堂av天堂久久久|
婷婷久久香蕉五月综合加勒比|
亚洲国产精品久久电影欧美|
伊人久久综合成人网|
国产精品岛国久久久久|
欧美久久综合九色综合|
久久久无码精品亚洲日韩蜜臀浪潮|
久久综合综合久久97色|
日韩欧美亚洲综合久久
|
国产精品女同一区二区久久|
久久精品国产一区二区电影|
精品久久久久久亚洲精品
|
99久久无码一区人妻a黑|
91精品国产色综久久|
av午夜福利一片免费看久久|
久久国产免费直播|
久久精品一本到99热免费|
久久精品亚洲乱码伦伦中文|
色综合久久久久综合体桃花网|
久久精品成人欧美大片|
国产精品久久久福利|
yy6080久久|
天天影视色香欲综合久久|
久久精品国产一区二区三区日韩|
国产成人精品白浆久久69|
亚洲国产成人精品无码久久久久久综合|
亚洲色婷婷综合久久|
亚洲国产成人乱码精品女人久久久不卡
|
青青青青久久精品国产|
欧美牲交A欧牲交aⅴ久久|
亚洲中文字幕无码久久精品1|
国产精品伦理久久久久久
|
性高湖久久久久久久久AAAAA|
久久精品视频网|
久久96国产精品久久久|
久久99精品久久久久久久不卡|
久久综合九色综合网站|
亚洲欧美另类日本久久国产真实乱对白|
亚洲成色999久久网站|
热久久这里只有精品|
国产精品成人无码久久久久久
|