• <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++博客 ::
首頁 ::
聯(lián)系 ::
聚合
 ::
管理

			
			
			
				

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

			            		
		
            
	
            

            


            

            
	
            
	
		
		

            常用鏈接
            


            留言簿(4)
            



            我參與的團隊
            

            
	

            





            搜索
            

              
	
            • 
		
            •  
	
              • 

            


            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


	
            		
	
					

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

            思想：
            最大堆和最小堆：
            本文以最大堆作為介紹，主要的函數(shù) max_heapify 和 heap_sort  利用遞歸
            max_heapify函數(shù)的主要作用是調(diào)整對的結(jié)構(gòu)，是其滿足最大堆的性質(zhì)（其中利用遞歸），
            max_heapify（int i，int len）len參數(shù)是數(shù)組的個數(shù)，i參數(shù)是“備用根”的下標。

            代碼：

              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}

            別人的實現(xiàn)：
            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 閱讀(756) 評論(0)  編輯 收藏 引用  所屬分類: Algorithms 
	
            

            







            
	    
    




            






            

				

            

            



    
    







            
	   
	



久久久黄色大片|
亚洲成色www久久网站夜月|
婷婷久久精品国产|
激情久久久久久久久久|
日韩精品久久久久久|
2021久久国自产拍精品|
国产精品久久久久久影院|
青青草原精品99久久精品66|
MM131亚洲国产美女久久|
一级做a爰片久久毛片16|
久久嫩草影院免费看夜色|
亚洲人成无码久久电影网站|
性欧美大战久久久久久久久
|
久久天天躁狠狠躁夜夜avapp|
久久精品国产久精国产|
欧美久久综合性欧美|
99re久久精品国产首页2020|
久久96国产精品久久久|
久久国产精品一区|
一级a性色生活片久久无少妇一级婬片免费放|
国产精品毛片久久久久久久|
国产精品久久久久久久久|
亚洲成人精品久久|
亚洲国产成人精品91久久久|
久久久久亚洲av综合波多野结衣|
色婷婷综合久久久久中文
|
99久久精品国产一区二区|
久久精品国产精品亚洲精品|
国产精品久久久99|
伊人久久大香线焦AV综合影院|
国产亚洲美女精品久久久久狼|
国产精品久久久久久福利漫画|
国产69精品久久久久9999|
久久久免费观成人影院|
日产精品久久久久久久|
99久久精品国产综合一区|
色播久久人人爽人人爽人人片aV|
久久久久亚洲AV无码麻豆|
欧美午夜精品久久久久久浪潮|
亚洲人成伊人成综合网久久久
|
久久婷婷成人综合色综合|