首页 > 其他 > 详细

堆排序

时间:2014-01-15 23:48:49      阅读:515      评论:0      收藏:0      [点我收藏+]

  #返回上一级

@Author: 张海拔

@Update: 2014-01-12

@Link: http://www.cnblogs.com/zhanghaiba/p/3515570.html

 

bubuko.com,布布扣
 1 /*
 2  *Author: ZhangHaiba
 3  *Date: 2014-1-12
 4  *File: heap_sort.c
 5  *
 6  *a demo of heap data struct and heap sort
 7  */
 8 #include <stdio.h>
 9 #define N 512
10 
11 //public
12 void repair_heap(int*, int, int);
13 void create_heap(int*, int);
14 void heap_sort(int*, int);
15 //private
16 void swap(int*, int*);
17 
18 int heap[N];
19 
20 int main(void)
21 {
22     int n;
23 
24     scanf("%d", &n);
25     set_array(heap, n);
26     create_heap(heap, n);
27     heap_sort(heap, n);
28     return 0;
29 }
30 
31 void repair_heap(int *h, int n, int par)
32 {
33     int pmin, save, left, right;
34 
35     while (par <= n/2) {
36         save = h[par];
37         pmin = par; //now point to par
38         left = par*2;
39         right = left+1;
40         if (h[left] < h[par])
41             h[par] = h[pmin = left]; //now point to left
42         if (right <= n && h[right] < h[par])
43             h[par] = h[pmin = right]; //now point to right
44         if (pmin == par) //if ture means par point to root of a heap
45             break;
46         else
47             h[pmin] = save; //swap fininsed
48         par = pmin;
49     }
50 }
51 
52 void create_heap(int *h, int n)
53 {
54     int i;
55     
56     for (i = n/2; i != 0; --i)
57         repair_heap(h, n, i);
58 }
59 
60 //after heap sort, original heap becomes a descending array
61 //in this procession, we output a ascending order of heap data;
62 void heap_sort(int *h, int n)
63 {
64     while (n != 0) {
65         printf(n == 0 ? "%d\n" : "%d ", h[1]);
66         swap(&h[1], &h[n--]);
67         repair_heap(h, n, 1);
68     }
69 }
70 
71 //set array range [1, n]
72 int set_array(int *a, int n)
73 {
74     int i;
75     
76     for (i = 1; i <= n; ++i)
77         scanf("%d", a+i);
78 }
79 
80 void swap(int *a, int *b)
81 {
82     int tmp = *a;
83     *a = *b;
84     *b = tmp;
85 }
bubuko.com,布布扣

 

堆的定义:
1)首先,逻辑关系上它是完全二叉树,物理存储是静态线性表(数组)
2)其次,父母结点的值一定大于(小于)孩子结点的值

为了形象,下面把数组的下标说成指针,即广义的指针

指针从1开始,有如下性质:
1)父母结点的指针范围:[1, n/2]
2)叶子结点的指针范围:[n/2+1, n]
3)左孩子指针可由其父母指针计算:left = par*2;
4)右孩子存在的条件:right <= n;

怎么把一个数组(完全二叉树的存储)变成堆?
1)自顶向下调整(可能需要回溯往上调整)
2)自底向上调整(一定顺序往下调整)
因此采用自底向上调整

注意:

自底向上调整堆,是对堆整体来说的。
而对于单个结点的调整,是从上往下的。

 

这里用自底向上调整的方法实现了小根堆。

排序过程是堆顶元素与“堆尾”元素(完全二叉树最右下方的节点)交换,交换前输出,交换后调整规模减1的堆顶。

堆排序的核心是repair_heap(),这个函数的while循环中对par所指的节点进行堆调整——

pmin指针的意义是指向当前的树根、左子树根和右子树根三者中的值最小的节点。

pmin初始指向par,经过判断,pmin可能指向left,也可能指向right,也可能仍指向par。

若仍指向par,说明par比两个孩子的值都大,即par所指的已经是堆了,因此不需要再调整。(因为堆是自底向上创建的)

否则pmin指向了最小节点,完成交换后,当前par应该变为pmin。

理解了上面的过程,用递归来实现也是很简单的。

 

 #返回上一级

堆排序

原文:http://www.cnblogs.com/zhanghaiba/p/3515570.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!