Networking /C++/Linux
  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  11 Posts :: 14 Stories :: 1 Comments :: 0 Trackbacks

常用链接

留言簿(4)

我参与的团队

随笔分类

随笔档案

文章分类

文章档案

Edit

算法

搜索

  •  

最新评论

阅读排行榜

评论排行榜
heap sort (Heap 的build，排序)
堆实际上是一个数组对象，可以被视为一个完全二叉树，有完全二叉树的遍历得到（算法导论第六章）

思想：
最大堆和最小堆：
本文以最大堆作为介绍，主要的函数 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 阅读(731) 评论(0)  编辑 收藏 引用 所属分类: Algorithms

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理