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

            







            
	    
    




            






            

				

            

            



    
    







            
	   
	



久久天天躁狠狠躁夜夜躁2014|
久久久久国产精品嫩草影院|
国产精品久久久久a影院|
色老头网站久久网|
久久精品国产亚洲AV电影|
久久久青草青青亚洲国产免观|
久久无码国产|
久久精品中文字幕无码绿巨人|
久久国产精品久久精品国产|
国产精久久一区二区三区|
中文字幕无码久久人妻|
国产精品99久久免费观看|
免费一级欧美大片久久网
|
奇米影视7777久久精品人人爽|
亚洲狠狠婷婷综合久久久久|
久久99国产精品成人欧美|
亚洲精品国产美女久久久|
精品久久久久一区二区三区|
久久亚洲日韩精品一区二区三区|
AA级片免费看视频久久|
国产精品禁18久久久夂久|
欧美精品久久久久久久自慰|
久久人人爽人人爽人人片AV东京热|
国产精品久久久久影视不卡|
老色鬼久久亚洲AV综合|
久久久久久久久久久|
亚洲欧美另类日本久久国产真实乱对白
|
中文字幕无码av激情不卡久久|
一本色道久久88加勒比—综合|
色婷婷久久综合中文久久蜜桃av|
亚洲国产成人乱码精品女人久久久不卡
|
久久亚洲中文字幕精品一区|
青青青国产精品国产精品久久久久|
久久亚洲精品无码AV红樱桃|
狠狠精品久久久无码中文字幕|
香蕉99久久国产综合精品宅男自|
国内精品久久久久久久亚洲|
66精品综合久久久久久久|
99久久免费只有精品国产|
99久久精品这里只有精品|
国产精品一区二区久久精品无码
|