• <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 閱讀(998) 評論(0)  編輯 收藏 引用  所屬分類: 數據結構與算法 
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



国产麻豆精品久久一二三|
 久久综合狠狠综合久久激情 |
久久91亚洲人成电影网站|
久久伊人中文无码|
亚洲va中文字幕无码久久不卡|
国产精品无码久久四虎|
亚洲精品无码久久毛片|
久久天堂AV综合合色蜜桃网|
久久久久免费精品国产|
久久国产精品成人影院|
国产毛片久久久久久国产毛片
|
久久精品国产亚洲AV电影|
久久福利青草精品资源站免费
|
日韩乱码人妻无码中文字幕久久
|
精品午夜久久福利大片|
久久久久99精品成人片牛牛影视
|
国产免费久久精品丫丫|
久久精品一本到99热免费|
超级碰久久免费公开视频|
日韩久久久久久中文人妻|
国内精品免费久久影院|
国产精品岛国久久久久|
久久精品国产久精国产果冻传媒|
久久婷婷五月综合97色一本一本|
久久国产乱子伦精品免费强|
久久中文精品无码中文字幕|
久久精品无码午夜福利理论片|
久久综合久久综合亚洲|
亚洲综合久久综合激情久久
|
久久久久人妻一区二区三区|
99久久国产主播综合精品|
九九精品99久久久香蕉|
亚洲国产精品成人AV无码久久综合影院
|
久久久久亚洲av成人网人人软件
|
日韩人妻无码精品久久久不卡
|
99久久精品免费看国产一区二区三区|
狠狠干狠狠久久|
久久婷婷五月综合色高清|
久久婷婷国产剧情内射白浆|
日本亚洲色大成网站WWW久久|
久久久久国产亚洲AV麻豆|