Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3233652
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8557
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: C/C++

2011-02-23 22:04:19

本文给出的代码是最大堆。二话不说,上代码。

  1 #include
  2 #include
  3 #include
  4 #include
  5 inline void exchange(int* a,int *b)
  6 {
  7         int tmp;
  8         if(*a != *b)
  9         {
 10                 tmp   = *a;
 11                 *a    = *b;
 12                 *b    = tmp;
 13         }
 14         return ;
 15 }
 16 
 17 int findmaxpos(int *array,int pos,int len)
 18 {
 19         int left = pos*2;
 20         int right = pos*2+1;
 21         int max = array[pos];
 22         int ret = pos;
 23         if(left <= len && max
 24         {
 25                 ret = left;
 26                 max = array[left];
 27         }
 28 
 29         if(right <= len && max
 30         {
 31                 ret = right;
 32                 max = array[right];
 33         }
 34 
 35         return ret;
    }
 37 int heapify(int *array,int pos,int len)
 38 {
 39 
 40         int maxpos = findmaxpos(array,pos,len);
 41 
 42 
 43         if(pos != maxpos)
 44         {
 45                 exchange(&array[pos],&array[maxpos]);
 46                 heapify(array,maxpos,len);
 47 
 48         }
 49         return 0;
 50 }
 51 
 52 int buildheap(int *array,int len)
 53 {
 54         int i ;
 55         for(i = (len/2);i>0;i--)
 56         {
 57                 heapify(array,i,len);
 58 
 59         }
 60         return 0;
 61 }
 62 
 63 int heapsort(int *array,int len)
 64 {
 65         int i;
 66 
 67         buildheap(array,len);
 68         for (i = len;i>1;i--)
 69         {
 70                 exchange(&array[1],&array[i]);
 71                 len--;
 72                 heapify(array,1,len);
 73         }
 74         return 0;
 75 }
 76 
 77 
 78 int test_heapsort()
 79 {
 80         int array[11] = {0,16,14,10,8,7,9,3,2,4,1};
 81         int i;
 82         for(i = 1;i<=10;i++)
 83         {
 84                 printf("%d\t",array[i]);
 85         }
 86         printf("\n");
 87 
 88         heapsort(array,10);
 89         for(i = 1;i<=10;i++)
 90         {
 91                 printf("%d\t",array[i]);
 92         }
 93         printf("\n");
 94         return 0;
 95 
 96 }
 97 int test_buildheap()
 98 {
 99         int array[11] = { 0 , 4, 1,3,2,16,9,10,14,8,7};
100 
101         buildheap(array,10);
102 
103         assert(array[1] == 16);
104         assert(array[5] == 7);
105         assert(array[7]== 3);
106         assert(array[9] = 2);
107 
108         return 0;
109 }
110 
111 int test_heapify()
112 {
113         int array[11] = {0,16,4,10,14,7,9,3,2,8,1};
114         heapify(array,2,10);
115 
116         assert(array[1] = 16);
117 
118         assert(array[2] = 14);
119 
120         assert(array[4] = 8);
121 
122         assert(array[8] = 2);
123 
124         return 0;
125 }
126 int test_findmaxpos()
127 {
128         int array[5] = {0,1,8, 4, 3};
129         int a = findmaxpos(array,1,4);
130         assert (a == 2);
131         return 0;
132 }
133 int test_exchange()
134 {
         int a = 3;
136         int b = 5;
137         exchange(&a,&b);
138         assert(a == 5 );
139         assert(b == 3);
140         return 0;
141 }
142 int test()
143 {
144         test_exchange();
145         test_findmaxpos();
146         test_heapify();
147         test_buildheap();
148         test_heapsort();
149         return 0;
150 
151 }
152 int main(int argc,char *argv[])
153 {
154         test();
155         return 1;
156 }


阅读(1890) | 评论(1) | 转发(1) |
给主人留下些什么吧!~~

chinaunix网友2011-03-06 13:32:09

很好的, 收藏了 推荐一个博客,提供很多免费软件编程电子书下载: http://free-ebooks.appspot.com