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

            







            
	    
    




            






            

				

            

            



    
    







            
	   
	



伊人久久大香线焦综合四虎|
97精品伊人久久大香线蕉app|
色综合合久久天天综合绕视看
|
久久国产美女免费观看精品|
国产综合精品久久亚洲|
久久久WWW成人|
亚洲狠狠婷婷综合久久蜜芽|
狠狠狠色丁香婷婷综合久久俺|
久久99精品国产99久久6|
久久久久久国产精品美女|
国产午夜精品理论片久久影视|
中文字幕精品久久|
九九久久99综合一区二区|
久久久久99这里有精品10|
国产精品久久波多野结衣|
日本精品久久久久久久久免费|
国内精品久久久久久99蜜桃|
一97日本道伊人久久综合影院|
国内精品久久久久影院优|
亚洲国产精品综合久久网络|
97精品国产91久久久久久|
久久国产亚洲精品|
久久中文字幕视频、最近更新
|
久久精品女人天堂AV麻|
99久久人妻无码精品系列|
久久久国产视频|
久久人人爽人人爽人人片AV麻豆
|
国产精品福利一区二区久久|
久久夜色精品国产www|
亚洲精品国产成人99久久|
99久久99这里只有免费费精品|
久久国产色av免费看|
久久只这里是精品66|
婷婷久久综合九色综合九七|
国产精品成人久久久久三级午夜电影|
国内精品伊人久久久久AV影院|
伊人久久大香线焦AV综合影院|
久久精品综合网|
综合久久国产九一剧情麻豆|
综合久久精品色|
国产毛片欧美毛片久久久|