• <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>
            隨筆 - 70  文章 - 160  trackbacks - 0

            公告:
            知識共享許可協議
            本博客采用知識共享署名 2.5 中國大陸許可協議進行許可。本博客版權歸作者所有,歡迎轉載,但未經作者同意不得隨機刪除文章任何內容,且在文章頁面明顯位置給出原文連接,否則保留追究法律責任的權利。 具體操作方式可參考此處。如您有任何疑問或者授權方面的協商,請給我留言。

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            搜索

            •  

            積分與排名

            • 積分 - 179374
            • 排名 - 147

            最新評論

            閱讀排行榜

            評論排行榜

            建議先看看前言:http://m.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html

            上一章總結是的堆排序算法,這一章同樣是利用了堆這種數據結構,實現在是優先級隊列

            根據堆分為最大堆,最小堆,所以優先級隊列也可以分為最大優先級隊列最小優先級隊列

            優先級隊列的概念和用途書上已經寫的很清楚了,我就不再打一遍了。直接寫出具體實現。

            在實現前先說幾點:

            1.上一章說過,堆的length和heapsize要區分清楚,這一章的優先級隊列里就用到了。

            2.優先級隊列用到了上一章的一些函數比如MaxHeapify(),不記得的可以復習下上一章。

            以下是代碼及講解(此處實現的是最大優先級隊列):

            // 堆應用之優先級隊列
            // Tanky Woo
            // Blog: www.WuTianQi.com
            #include <iostream>
            using namespace std;
            const int INF = 999999;
             
            /////////////////////////////////////////////////////////
            ////////////// 以下代碼在堆排序中已講解過 ///////////////
            void MaxHeapify(int *a, int i, int len)
            {
                
            int lt = 2*i, rt = 2*i+1;
                
            int largest;
                
            if(lt <= len && a[lt] > a[i])
                    largest 
            = lt;
                
            else
                    largest 
            = i;
                
            if(rt <= len && a[rt] > a[largest])
                    largest 
            = rt;
                
            if(largest != i)
                {
                    
            int temp = a[i];
                    a[i] 
            = a[largest];
                    a[largest] 
            = temp;
                    MaxHeapify(a, largest, len);
                }
            }
             
            void BuildMaxHeap(int *a, int size)
            {
                
            for(int i=size/2; i>=1--i)
                    MaxHeapify(a, i, size);
            }
             
            void PrintArray(int data[], int size)
            {
                
            for (int i=1; i<=size; ++i)
                    cout 
            <<data[i]<<"  ";
                cout
            << endl << endl;
            }
            ////////////////////////////////////////////////////////////
             
            // 返回具有最大關鍵字的元素
            int HeapMaximum(int *a)
            {
                
            return a[1];
            }
             
            // 去掉并返回具有最大關鍵字的元素
            // 注意:這里每次MaxHeapify的是heapsize
            int HeapExtractMax(int *a, int &heapsize)
            {
                
            if(heapsize < 1)
                    cout 
            << "Heap Underflow" << endl;
                
            int max = a[1];
                a[
            1= a[heapsize];
                
            --heapsize;
                MaxHeapify(a, 
            1, heapsize);
                
            return max;
            }
             
            // 將元素a[i]的值增加到key
            void HeapIncreaseKey(int *a, int i, int key)
            {
                
            if(key < a[i])
                    cout 
            << "New key is smaller than current key" << endl;
                a[i] 
            = key;
                
            while(i > 1 &&a[i/2< a[i])
                {
                    
            int temp = a[i];
                    a[i] 
            = a[i/2];
                    a[i
            /2= temp;
                    i 
            /= 2;
                }
            }
             
            // 插入關鍵字為key的元素
            void MaxHeapInsert(int *a, int key, int &heapsize)
            {
                
            ++heapsize;
                a[heapsize] 
            = -INF;
                HeapIncreaseKey(a, heapsize, key);
            }
             
             
             
            int main()
            {
                
            int len, heapsize;
                
            int arr[100= {0151395128740621};
                
            // 區別len 和 heapsize
                
            // heapsize是堆的大小,而len是初始數組的總大小。
                len = heapsize = 12;
             
                
            // 首先建堆
                BuildMaxHeap(arr, len);
                cout 
            << "建堆后: " << endl;
                PrintArray(arr, len);
             
                
            // 使用HeapMaximum
                cout << "當前最大的元素是: " << endl;
                cout 
            << HeapMaximum(arr) << endl << endl;
             
                
            // 使用HeapExtractMax
                cout << "使用HeapExtractMax后: " << endl;
                HeapExtractMax(arr,heapsize);
                PrintArray(arr, heapsize);
             
                
            // 再次使用HeapExtractMax
                cout << "再次使用HeapExtractMax后: " << endl;
                HeapExtractMax(arr,heapsize);
                PrintArray(arr, heapsize);
             
                
            // 使用HeapIncreaseKey
                cout << "使用HeapIncreaseKey后: " << endl;
                HeapIncreaseKey(arr, 
            215);
                PrintArray(arr, heapsize);
             
                
            // 使用MaxHeapInsert
                cout << "使用MaxHeapInsert后: " << endl;
                MaxHeapInsert(arr, 
            28, heapsize);
                PrintArray(arr, heapsize);
            }

            以下是運行結果:

            youxianji

            看上圖的結果:

            在第二次使用HeapExtractMax后,把第二個數字即6設為15,更新后,結果就是HeapIncreaseKey的輸出。

            Tanky Woo 標簽:

            個人Blog同步發表: http://www.wutianqi.com/?p=2349
            posted on 2011-04-17 15:00 Tanky Woo 閱讀(1524) 評論(0)  編輯 收藏 引用
            久久久国产精品亚洲一区| 久久精品男人影院| 日韩亚洲国产综合久久久| 性色欲网站人妻丰满中文久久不卡| 色婷婷综合久久久久中文| 国产999精品久久久久久| 亚洲国产精品成人久久| 精品少妇人妻av无码久久| 亚洲狠狠婷婷综合久久蜜芽| 亚洲av日韩精品久久久久久a | 人妻系列无码专区久久五月天| 久久久久久久久久免免费精品| 国产欧美一区二区久久| 青青草原综合久久大伊人导航| 久久亚洲中文字幕精品有坂深雪| 久久国产成人| 精品国产青草久久久久福利| 99精品久久久久久久婷婷| 久久久久亚洲AV无码观看| 香蕉99久久国产综合精品宅男自| 日产精品久久久久久久| 亚洲?V乱码久久精品蜜桃| 91精品国产91久久久久久青草| 青青热久久综合网伊人| 色综合久久综精品| 久久综合久久自在自线精品自| 亚洲国产成人久久综合野外| 久久久久久久久久久精品尤物| 久久AAAA片一区二区| 国产福利电影一区二区三区久久久久成人精品综合 | 93精91精品国产综合久久香蕉| 中文字幕久久波多野结衣av| 亚洲精品NV久久久久久久久久 | 久久久久久青草大香综合精品| 热99re久久国超精品首页| 日本一区精品久久久久影院| 精品999久久久久久中文字幕 | 伊人久久大香线蕉综合5g| 久久久久97国产精华液好用吗| 久久久免费观成人影院| 久久婷婷是五月综合色狠狠|