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





            
	    
    




            






            

				

            


    
    







            
	   
	



精品久久一区二区三区|
久久久久无码专区亚洲av|
亚洲日本va午夜中文字幕久久|
久久黄视频|
伊人久久一区二区三区无码|
色婷婷综合久久久久中文
|
久久99精品国产自在现线小黄鸭|
亚洲AV无码一区东京热久久|
久久青青草原国产精品免费|
久久久久久久久久免免费精品
|
91精品国产色综久久|
亚洲欧美成人久久综合中文网
|
91久久国产视频|
欧美成人免费观看久久|
高清免费久久午夜精品|
亚洲欧美国产日韩综合久久|
精品熟女少妇av免费久久|
久久人人爽人人精品视频|
青草国产精品久久久久久|
久久久精品国产Sm最大网站|
精品久久久久久亚洲精品|
亚洲精品97久久中文字幕无码|
国产精品青草久久久久婷婷|
久久精品国产亚洲AV蜜臀色欲
|
欧美激情精品久久久久|
国产亚洲精品久久久久秋霞|
色偷偷88欧美精品久久久|
久久精品国产半推半就|
国产精品免费福利久久|
久久精品国产亚洲77777|
欧美国产成人久久精品|
人人狠狠综合久久亚洲|
精品国产婷婷久久久|
一本久久a久久精品综合夜夜
|
国产精品VIDEOSSEX久久发布|
久久国产精品无码一区二区三区
|
人妻少妇久久中文字幕|
伊人久久综合精品无码AV专区|
香蕉久久影院|
97久久国产综合精品女不卡|
人妻无码αv中文字幕久久
|