• <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

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

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            搜索

            •  

            積分與排名

            • 積分 - 179442
            • 排名 - 147

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

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

            上一章總結(jié)是的堆排序算法,這一章同樣是利用了堆這種數(shù)據(jù)結(jié)構(gòu),實(shí)現(xiàn)在是優(yōu)先級(jí)隊(duì)列。

            根據(jù)堆分為最大堆,最小堆,所以優(yōu)先級(jí)隊(duì)列也可以分為最大優(yōu)先級(jí)隊(duì)列最小優(yōu)先級(jí)隊(duì)列

            優(yōu)先級(jí)隊(duì)列的概念和用途書(shū)上已經(jīng)寫(xiě)的很清楚了,我就不再打一遍了。直接寫(xiě)出具體實(shí)現(xiàn)。

            在實(shí)現(xiàn)前先說(shuō)幾點(diǎn):

            1.上一章說(shuō)過(guò),堆的length和heapsize要區(qū)分清楚,這一章的優(yōu)先級(jí)隊(duì)列里就用到了。

            2.優(yōu)先級(jí)隊(duì)列用到了上一章的一些函數(shù)比如MaxHeapify(),不記得的可以復(fù)習(xí)下上一章。

            以下是代碼及講解(此處實(shí)現(xiàn)的是最大優(yōu)先級(jí)隊(duì)列):

            // 堆應(yīng)用之優(yōu)先級(jí)隊(duì)列
            // Tanky Woo
            // Blog: www.WuTianQi.com
            #include <iostream>
            using namespace std;
            const int INF = 999999;
             
            /////////////////////////////////////////////////////////
            ////////////// 以下代碼在堆排序中已講解過(guò) ///////////////
            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;
            }
            ////////////////////////////////////////////////////////////
             
            // 返回具有最大關(guān)鍵字的元素
            int HeapMaximum(int *a)
            {
                
            return a[1];
            }
             
            // 去掉并返回具有最大關(guān)鍵字的元素
            // 注意:這里每次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;
                }
            }
             
            // 插入關(guān)鍵字為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};
                
            // 區(qū)別len 和 heapsize
                
            // heapsize是堆的大小,而len是初始數(shù)組的總大小。
                len = heapsize = 12;
             
                
            // 首先建堆
                BuildMaxHeap(arr, len);
                cout 
            << "建堆后: " << endl;
                PrintArray(arr, len);
             
                
            // 使用HeapMaximum
                cout << "當(dāng)前最大的元素是: " << 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);
            }

            以下是運(yùn)行結(jié)果:

            youxianji

            看上圖的結(jié)果:

            在第二次使用HeapExtractMax后,把第二個(gè)數(shù)字即6設(shè)為15,更新后,結(jié)果就是HeapIncreaseKey的輸出。

            Tanky Woo 標(biāo)簽: ,,

            個(gè)人Blog同步發(fā)表: http://www.wutianqi.com/?p=2349
            posted on 2011-04-17 15:00 Tanky Woo 閱讀(1524) 評(píng)論(0)  編輯 收藏 引用
            久久99精品国产麻豆蜜芽| 色综合久久中文字幕综合网| 亚洲香蕉网久久综合影视| 国产亚洲精久久久久久无码77777| 99久久精品国产一区二区| 99久久精品国产麻豆| 蜜臀久久99精品久久久久久| 亚洲AV乱码久久精品蜜桃| 久久久青草久久久青草| 伊人久久大香线蕉综合影院首页| 久久精品水蜜桃av综合天堂| 久久露脸国产精品| 久久天堂电影网| 亚洲国产另类久久久精品小说| 国产精品成人无码久久久久久 | 久久久精品人妻无码专区不卡| 久久精品免费一区二区| 99久久99久久精品国产片| 99久久夜色精品国产网站| 久久九色综合九色99伊人| 777米奇久久最新地址| 无码人妻久久一区二区三区免费 | 国产精品无码久久综合| 欧美精品丝袜久久久中文字幕| 国产精品久久久久jk制服| 97精品国产97久久久久久免费| 香蕉99久久国产综合精品宅男自 | 久久久久久久亚洲Av无码| 久久一区二区免费播放| 99久久精品免费| 久久亚洲欧美日本精品| 国产精品一区二区久久国产| 人妻无码αv中文字幕久久琪琪布 人妻无码久久一区二区三区免费 人妻无码中文久久久久专区 | 国产精品伊人久久伊人电影 | 99久久国产热无码精品免费久久久久 | 久久99九九国产免费看小说| 久久精品国产福利国产秒| 国产精品久久久久无码av | 精品免费久久久久久久| 国产精品女同久久久久电影院| 久久久婷婷五月亚洲97号色|