• <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)  編輯 收藏 引用
            久久久久久免费视频| 久久久国产乱子伦精品作者| 久久精品国产亚洲AV影院| 品成人欧美大片久久国产欧美| 一本色道久久88精品综合| 久久亚洲AV无码精品色午夜麻豆 | 少妇人妻综合久久中文字幕| 青青青国产精品国产精品久久久久 | 亚洲国产精品无码久久久久久曰 | 性做久久久久久久久浪潮| 久久免费精品一区二区| 国内精品久久久久久99蜜桃| 亚洲va中文字幕无码久久| 久久99热这里只频精品6| 久久伊人五月天论坛| 久久久午夜精品| 久久久噜噜噜久久中文字幕色伊伊 | 国产精品一区二区久久不卡| 久久婷婷五月综合97色| 久久人人爽人人爽人人AV东京热| 久久中文骚妇内射| 精品久久久久久国产91| 中文字幕一区二区三区久久网站| 品成人欧美大片久久国产欧美...| 久久久久国产一区二区| 亚洲精品WWW久久久久久| 久久亚洲中文字幕精品一区| 久久精品中文闷骚内射| 亚洲国产精久久久久久久| 久久国产精品波多野结衣AV| 国内精品久久久久久久久电影网| 久久久无码精品亚洲日韩蜜臀浪潮| 久久香蕉一级毛片| 一97日本道伊人久久综合影院| 热re99久久6国产精品免费| 久久久久久久尹人综合网亚洲| 日本精品久久久久影院日本| 久久精品国产清高在天天线| 青青热久久国产久精品 | 91精品国产乱码久久久久久| 久久激情亚洲精品无码?V|