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

    
            

            




            







												


        

            
	

            
	
            
		
            
			
				
            Networking /C++/Linux
            
				
            
			            		
		
            
	
            

            

            
	
            
		
            
			
				
 
C++博客 ::
首頁 ::
聯系 ::
聚合
 ::
管理

			
			
			
				

	
            
		
            
			
			
			
				 
				11 
				Posts ::
				14 Stories
				::
				1 Comments
				::
				0 Trackbacks
			
		
            
	
            

			            		
		
            
	
            

            


            

            
	
            
	
		
		

            常用鏈接
            


            留言簿(4)
            



            我參與的團隊
            

            
	

            





            搜索
            

              
	
            • 
		
            •  
	
              • 

            


            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


	
            		
	
					

            
			
	
	
            
		堆實際上是一個數組對象，可以被視為一個完全二叉樹，有完全二叉樹的遍歷得到（算法導論第六章）

            思想：
            最大堆和最小堆：
            本文以最大堆作為介紹，主要的函數 max_heapify 和 heap_sort  利用遞歸
            max_heapify函數的主要作用是調整對的結構，是其滿足最大堆的性質（其中利用遞歸），
            max_heapify（int i，int len）len參數是數組的個數，i參數是“備用根”的下標。

            代碼：

              1#include<iostream>
              2#include<stdlib.h>
              3#include<time.h>
              4using namespace std;
              5
              6class heap{
              7public: 
              8        heap()
              9        {
             10                a=NULL;
             11                size=10;
             12                heap(size);
             13        }
             14        
             15        heap(int size_t):size(size_t)
             16        {
             17                a=new int[size+1];
             18                srand(time(NULL));
             19                
             20                for(int i=1;i<=size;i++)
             21                {
             22                        a[i]=rand()%1000;
             23                }
             24        }
             25        
             26       /* heap(int *b)
             27        {
             28                int len=sizeof(b);
             29                size=len;
             30                a=new int[size+1];
             31                
             32                for(int i=1;i<=size;i++)
             33                {        
             34                        a[i]=b[i-1];
             35                }
             36        }*/
             37        
             38        ~heap()
             39        {
             40                cout<<"Destroy..\n";
             41                delete []a;
             42                a=NULL;
             43        }
             44        
             45        void max_heapify(int i,int len);
             46        void build_heap();
             47        void heap_sort();
             48        
             49        
             50        void print();
             51        
             52        int left(int i){return 2*i;}
             53        int right(int i){return 2*i+1;}
             54        int parent(int i ){return i/2;}        
             55private:
             56        int *a;
             57        int size;
             58}            ;
             59
             60void heap::heap_sort()
             61{
             62        int len=size;
             63        int t;
             64        
             65        for(int i=size;i>=2;i--)
             66        {
             67                t=a[1];
             68                a[1]=a[i];
             69                a[i]=t;
             70                
             71                len--;
             72                
             73                max_heapify(1,len);
             74        }
             75}
             76
             77
             78void heap::max_heapify(int i,int len)
             79{
             80        int lt,rt;
             81        int max=0;
             82        
             83        lt=left(i);
             84        rt=right(i);
             85        
             86        if(lt<=len&&a[lt]>a[i]){
             87                max=lt;
             88        }
             89        else{
             90                max=i;
             91        }
             92        
             93        if(rt<=len&&a[rt]>a[max]){
             94                max=rt;
             95        }
             96        
             97        if(max!=i){
             98                int t;
             99                t=a[i];
            100                a[i]=a[max];
            101                a[max]=t;
            102                
            103                max_heapify(max,len);
            104        }                  
            105}
            106
            107void heap::build_heap()
            108{
            109        for(int i=size/2;i>=1;i--)
            110        {
            111                max_heapify(i,size);
            112        }
            113}
            114
            115void heap::print()
            116{
            117        for(int i=1;i<=size;i++)
            118        {
            119                cout<<a[i]<<"\t";
            120        }
            121        cout<<endl;
            122}
            123
            124
            125int main()
            126{
            127        heap test(10);
            128       // test.print();
            129        
            130        
            131        //cout<<endl;
            132        test.build_heap();
            133        test.print();  
            134        
            135        cout<<endl;
            136        test.heap_sort();
            137        test.print() ;     
            138
            139}

            別人的實現：
            http://www.cnblogs.com/dolphin0520/archive/2011/10/06/2199741.html
            http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.4.2.2.htm
            http://www.cnblogs.com/lovemo1314/archive/2011/09/13/2175032.html

            
	
            
	
	
            
		posted on 2011-12-05 14:35 likun 閱讀(751) 評論(0)  編輯 收藏 引用  所屬分類: Algorithms 
	
            

            







            
	    
    




            






            

				

            

            



    
    







            
	   
	



一本综合久久国产二区|
久久亚洲国产精品123区|
91精品免费久久久久久久久|
久久国产一区二区|
亚洲综合久久久|
久久国产精品一区二区|
91精品免费久久久久久久久|
午夜视频久久久久一区|
久久av免费天堂小草播放|
亚洲精品无码久久久影院相关影片|
亚洲AV成人无码久久精品老人|
久久av无码专区亚洲av桃花岛|
国内精品久久久久久久97牛牛|
国产精品免费久久久久久久久|
久久91精品国产91久久户|
久久精品无码一区二区WWW|
久久久久99精品成人片牛牛影视|
欧美日韩中文字幕久久伊人|
国产精品久久久久影院色|
久久亚洲AV成人出白浆无码国产|
一本久道久久综合狠狠躁AV|
久久久久国产精品|
久久亚洲欧美国产精品|
欧美日韩精品久久久久|
精品国产乱码久久久久久呢|
99久久久久|
免费观看久久精彩视频|
人妻精品久久无码区|
亚洲精品无码久久久久|
精产国品久久一二三产区区别|
久久综合色区|
亚洲国产天堂久久综合|
一个色综合久久|
久久婷婷五月综合97色直播|
亚洲精品无码久久毛片|
亚洲精品tv久久久久久久久久|
久久这里只有精品视频99|
久久精品无码一区二区日韩AV|
精品久久国产一区二区三区香蕉|
国产精品99久久久久久董美香|
麻豆精品久久精品色综合|