• <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 閱讀(753) 評論(0)  編輯 收藏 引用  所屬分類: Algorithms 
	
            

            







            
	    
    




            






            

				

            

            



    
    







            
	   
	



久久人妻AV中文字幕|
伊人久久一区二区三区无码|
久久精品人人做人人爽97|
久久久亚洲欧洲日产国码aⅴ|
日本免费一区二区久久人人澡
|
国产精品成人无码久久久久久|
欧美久久综合九色综合|
99久久久精品免费观看国产|
久久综合精品国产一区二区三区|
久久九九兔免费精品6|
www亚洲欲色成人久久精品|
久久亚洲国产精品成人AV秋霞|
久久99精品国产99久久|
日本五月天婷久久网站|
91亚洲国产成人久久精品网址|
久久久亚洲AV波多野结衣|
99久久免费国产精品|
久久亚洲精品无码AV红樱桃|
天天做夜夜做久久做狠狠|
色噜噜狠狠先锋影音久久|
中文字幕久久久久人妻|
精品久久久久久无码中文字幕|
日本人妻丰满熟妇久久久久久|
久久精品国产99国产精品|
狠狠色丁香久久综合五月|
yy6080久久|
久久久黄片|
国产高潮国产高潮久久久91|
久久综合给合久久狠狠狠97色|
亚洲精品无码久久毛片|
国产国产成人久久精品|
色综合久久天天综合|
久久婷婷久久一区二区三区|
无码国内精品久久人妻|
亚洲欧美伊人久久综合一区二区
|
亚洲成色WWW久久网站|
色婷婷久久综合中文久久一本|
国产成人综合久久精品尤物|
国内精品久久久久影院优|
久久Av无码精品人妻系列|
婷婷五月深深久久精品|