Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1495313
  • 博文数量: 148
  • 博客积分: 2234
  • 博客等级: 大尉
  • 技术积分: 3225
  • 用 户 组: 普通用户
  • 注册时间: 2012-05-17 21:34
个人简介

未来很长。

文章存档

2017年(7)

2016年(4)

2015年(1)

2014年(6)

2013年(31)

2012年(99)

分类: C/C++

2012-05-29 18:51:22

算法思想:首先将与堆相应的完全二叉树根节点中的记录移出,该记录称为待调整记录,此时根节点相当于空节点,从空节点的左右孩子中选出一个关键字较大的记录,如果该记录的关键字大于待调整记录的关键字,则将该记录上移至空节点中。
此时,原来的那个关键字较大的节点相当于空节点,从空节点的左右孩子中选出一个关键字较大的记录,如果该记录的关键字仍大于待调整记录的关键字,则将该记录上移至空节点。
重复上述过程,直至空节点左右孩子的关键字均小于待调整记录的关键字,此时,将待调整记录放入空节点中,测试代码如下所示:

点击(此处)折叠或打开

  1. #include<stdio.h>
  2. #include<stdlib.h>

  3. void min_heapfy(int a[],int HEAPSIZE,int i)
  4. {
  5.     
  6.     int t;
  7.     int flag=1;
  8.     int j=2*i; //左孩子结点
  9.     t=a[i]; //暂存根记录
  10.     while(j<=HEAPSIZE&&flag)
  11.     {
  12.     
  13.         if((j+1)<=HEAPSIZE&&a[j]<a[j+1]) j++; //若存在右子树,且右子树根的关键字大,则沿右分支"筛选"

  14.      if(t>=a[j]) flag=0; //筛选完毕

  15.         else
  16.         {
  17.             a[i]=a[j];
  18.             i=j;
  19.             j=2*i;
  20.         } //继续筛选

  21.     }
  22.     a[i]=t; //将a[i]填入恰当的位置
  23. }
  24. void Create_min_heap(int a[],int length)//创建堆
  25. {
  26.     
  27.     int i;
  28.     for(i=length/2;i>=1;i--)/*自第[length/2]个记录开始进行筛选建堆*/
  29.         min_heapfy(a,length,i);
  30. }

  31. /*对a[1....n]进行堆排序,执行本算法后,a[]中记录按关键字由大到小排列*/
  32. void HeapSort(int a[],int length)
  33. {
  34.     int i,e;
  35.     Create_min_heap(a,length);
  36.     for(i=length;i>=1;--i)
  37.     {
  38.         printf("%4d",a[1]); //输出堆顶
  39.         e=a[1];                //将堆顶记录和堆中的最后一个记录进行交换
  40.         a[1]=a[i];
  41.         a[i]=e;
  42.         min_heapfy(a,i-1,1); //进行调整,使a[1....n-1]记录变成堆
  43.     }
  44. }
  45. int main()
  46. {
  47.     int a[100];
  48.     int i;
  49.     int length;    
  50.     printf("请输入元素个数 : ");
  51.     scanf("%d",&length);
  52.     
  53.     for(i=1;i<=length;i++)
  54.         scanf("%d",&a[i]);
  55.         
  56.     printf("\n");
  57.     Create_min_heap(a,length);

  58.     printf("创建好堆以后的数组元素如下所示: \n");
  59.     for(i=1;i<=length;i++)
  60.         printf("%4d",a[i]);
  61.     printf("\n");
  62.     printf("经过排序后的堆,数组元素如下所示 : \n");

  63.     HeapSort(a,8);    
  64.     printf("\n");

  65.     
  66. }

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