算法导论学习-heapsort

heap的定义：如果数组a[1,....n]满足：a[i]>a[2*i] && a[i]>a[2*i+1]，1<=i<=n/2，那么就是一个heap，而且是max-heap

heap有两种，max-heap 和 min-heap，其中min-heap的性质与上面所述相反，即 a[i]<a[2*i] && a[i]<a[2*i+1].

这里以max-heap为例说明heap的三种基本操作，即Max-Heap-Maintenance, Build-Max-Heap, HeapSort.

1. Max-Heap-Maintenance

input：数组A和下标indice（i）　　output：维护以 i 为根的子树的max-heap性质。

Max-Heap-Maintenance的伪代码如下：

以一个例图来解释上述程序的运行过程：

a) 图为heap的初始状态，现在执行程序Max-Heap-Maintenance（A，2）。node 2的值为4，比左孩子值14小，所以把A[2] 和 A[4]进行交换，这里虽然右孩子值为7，也比A[2]要大，但我们要找两个孩子中值最大的孩子，并且将父节点和它交换。交换完毕后，从被交换的孩子节点的位置出发，图中是A[4]，见图b），然后在该节点上重复上述操作，直至该节点是叶子节点，如图C），则终止程序。

2. Build-Max-Heap

因为每进行一次Max-Heap-Maintenance（i）操作，实际上都是建立以 i 为根节点的最大heap的一棵子树。所以我们自底向上建立最大heap，只有这样才能保证建立的heap具有max-heap性质。

3. Heap-Sort

首先先建立max-heap，但我们仍不能够根据max-heap得到排序结果，因为max-heap只能保证根节点值大于孩子节点的值，并没有孩子节点之间的大小关系比较。具体做法看伪代码+样例分析图。

最后贴上C++实现代码：

 1 #include<iostream>

 2 #include<algorithm>

 3 using namespace std;

 4 int a[101];

 5 int array_size,heap_size;

 6 int left(int i){

 7     return 2*i;

 8 }

 9 int right(int i){

10     return 2*i+1;

11 }

12 void Max_Heap_Maintenance(int i){

13     int l, r, largest=-1;

14     l=left(i);

15     r=right(i);

16     if(l>heap_size||r>heap_size) return;

17     if(l<=heap_size&&a[l]>a[i]){

18         largest=l;

19     }

20     else largest=i;

21     if(r<=heap_size&&a[r]>a[largest]){

22         largest=r;

23     }

24     if(largest!=i){

25         int tmp=a[largest];

26         a[largest]=a[i];

27         a[i]=tmp;

28         Max_Heap_Maintenance(largest);

29     }

30 }

31 void Build_Max_Heap(){

32     heap_size=array_size;

33     for(int i=array_size/2;i>=1;i--){

34         Max_Heap_Maintenance(i);

35     }

36 }

37 void Heap_Sort(){

38     Build_Max_Heap();

39     for(int i=array_size;i>=2;i--){

40         int tmp=a[i];

41         a[i]=a[1];

42         a[1]=tmp;

43         heap_size--;

44         Max_Heap_Maintenance(1);

45     }

46     int tmp=a[2];

47     a[2]=a[1];

48     a[1]=tmp;

49 }

50 int main(){

51     while(scanf("%d",&array_size)!=EOF){

52         for(int i=1;i<=array_size;i++){

53             scanf("%d",&a[i]);

54         }

55         Heap_Sort();

56         for(int i=1;i<=array_size;i++){

57             printf("%d ",a[i]);

58         }printf("\n");

59     }

60     return 0;

61 }

Code-HeapSort

巴特西

算法导论学习-heapsort

最新文章

热门文章