堆排序(Heap Sort)算法学习

在程序设计相关领域，堆(Heap)的概念主要涉及到两个方面：

一种数据结构，逻辑上是一颗完全二叉树，存储上是一个数组对象（二叉堆）。
垃圾收集存储区，是软件系统可以编程的内存区域。
本文所说的堆，指的是前者。

堆排序的时间复杂度是O(nlgN)，与快速排序达到相同的时间复杂度。但是在实际应用中，我们往往采用快速排序而不是堆排序。这是因为快速排序的一个好的实现，往往比堆排序具有更好的表现。堆排序的主要用途，是在形成和处理优先级队列方面。另外，如果计算要求是类优先级队列（比如，只要返回最大或者最小元素，只有有限的插入要求等），堆同样是很适合的数据结构。

基础知识
堆一般用数组表示，比如数组A数组的长度Length(A)，堆在数组中的元素个数HeapSize(A)。一般说来，HeapSize(A) <= Length(A)，因为数组A当中可能有一些元素不在堆中。

假设节点I是数组A中下标为i的节点。

Parent(i) : return Floor(i/2); //I的父节点下标，Floor(i)表示比i小的最大整数。
Left(i) : return 2*i; //I的左子节点
Right(i) : return 2*i+1; //I的右子节点
含有n个元素的堆A的高度是: Floor(lgn)。

堆的基本操作
MaxHeapify( A, i ):
保持堆的性质。假设数组A和下标i，假定以Left(i)和Right(i)为根结点的左右两棵子树都已经是最大堆，节点i的值可能小于其子节点。调整节点i的位置。

BuildMaxHeap( A ):
从一个给定的数组建立最大堆。子数组A[ floor(n/2)+1 .... ... n]中的元素都是树的叶节点(完全二叉树的基本性质)。从索引 ceiling(n/2)开始一直到1，对每一个元素都执行MaxHeapify，最终得到一个最大堆。

堆排序 HeapSort( A ):
堆排序算法的基本思想是，将数组A创建为一个最大堆，然后交换堆的根(最大元素)和最后一个叶节点x，将x从堆中去掉形成新的堆A1，然后重复以上动作，直到堆中只有一个节点。

优先级队列算法-增加某元素的值(优先级) : HeapIncreaseKey( A, i, key )
增加某一个元素的优先级后（元素的值），该元素应该向上移动，才能保持堆的性质。

优先级队列算法-插入一个元素: Insert( S, x ) 将x元素插入到优先级队列S中。
主要思路是，将堆的最后一个叶节点之后，扩展一个为无穷小的新叶节点，然后增大它的值为x的值。

堆排序实现原理






堆排序的C语言实现
view sourceprint?01 #include <stdio.h> 

02 #include <stdlib.h> 

03   

04 void HeapSort(int num[],int size); 

05 void BuildHeap(int num[] ,int size); 

06 void PercolateDown(int num[] , int index,int size); 

07 void PrintHeap(const char* strMsg,int array[],int nLength);  

08 void Swap(int num[] , int v, int u); 

09   

10 int main(int argc, char *argv[]) 

11 { 

12   int data[13]={8,5,4,6,13,7,1,9,12,11,3,10,2}; 

13   HeapSort(data,13); 

14     

15   system("PAUSE");   

16   return 0; 

17 } 

18   

19   

20 void HeapSort(int num[] ,int size) 

21 { 

22     int i; 

23     int iLength=size; 

24       

25     PrintHeap("Befor Sort:",num,iLength); 

26       

27     BuildHeap(num,size);// 建立小顶堆    

28       

29     for (i = iLength - 1; i >= 1; i--) {    

30         Swap(num, 0, i);// 交换    

31         size--;// 每交换一次让规模减少一次    

32         PercolateDown(num, 0,size);// 将新的首元素下滤操作  

33         PrintHeap("Sort Heap:",num,iLength);   

34     } 

35 } 

36   

37 // 建堆方法，只需线性时间建好    

38 void BuildHeap(int num[] ,int size) {  

39     int i;  

40     for (i = size / 2 - 1; i >= 0; i--) {// 对前一半的节点（解释为“从最后一个非叶子节点开始，将每个父节点都调整为最小堆”更合理一些）    

41         PercolateDown(num, i,size);// 进行下滤操作 

42         PrintHeap("Build heap:",num,size); 

43     }    

44 } 

45       

46 // 对该数进行下滤操作，直到该数比左右节点都小就停止下滤    

47 void PercolateDown(int num[] , int index,int size) {    

48     int min;// 设置最小指向下标    

49     while (index * 2 + 1<size) {// 如果该数有左节点，则假设左节点最小    

50         min = index * 2 + 1;// 获取左节点的下标    

51         if (index * 2 + 2<size) {// 如果该数还有右节点    

52             if (num[min] > num[index * 2 + 2]) {// 就和左节点分出最小者    

53                 min = index * 2 + 2;// 此时右节点更小，则更新min的指向下标    

54             }    

55         }    

56         // 此时进行该数和最小者进行比较，    

57         if (num[index] < num[min]) {// 如果index最小，    

58             break;// 停止下滤操作    

59         } else {    

60             Swap(num, index, min);// 交换两个数，让大数往下沉    

61             index = min;// 更新index的指向    

62         }    

63     }// while    

64 } 

65       

66 // 给定数组交换两个数的位置    

67 void Swap(int num[] , int v, int u) {   

68     int temp = num[v];    

69     num[v] = num[u];    

70     num[u] = temp;    

71 }    

72   

73 void PrintHeap(const char* strMsg,int array[],int nLength) 

74 { 

75      int i; 

76      printf("%s",strMsg); 

77      for(i=0;i<nLength;i++) 

78      { 

79         printf("%d ",array[i]); 

80      } 

81      printf("\n"); 

82 }

下面也是C语言的实现，稍微改动了下：

view sourceprint?01 #include <stdio.h> 

02 #include <stdlib.h> 

03   

04 void HeapSort(int num[],int size); 

05 void BuildHeap(int num[] ,int size); 

06 void PercolateDown(int num[] , int index,int size); 

07 void PrintHeap(const char* strMsg,int array[],int nLength);  

08 void Swap(int num[] , int v, int u); 

09   

10 int main(int argc, char *argv[]) 

11 { 

12   /* 将数组看成完全二叉树的中序遍历结果的线性存储 */

13   int data[13]={8,5,4,6,13,7,2,9,12,11,3,10,1}; 

14   HeapSort(data,13); 

15     

16   system("PAUSE");     

17   return 0; 

18 } 

19   

20   

21 void HeapSort(int num[] ,int size) 

22 { 

23     int i; 

24     int iLength=size; 

25       

26     PrintHeap("Befor Sort:",num,iLength); 

27       

28     BuildHeap(num,size);// 建立小顶堆    

29       

30     for (i = iLength - 1; i >= 1; i--) {    

31         Swap(num, 0, i);// 交换    

32         size--;// 每交换一次让规模减少一次    

33         PercolateDown(num, 0,size);// 将新的首元素下滤操作  

34         PrintHeap("Sort Heap:",num,iLength);   

35     } 

36 } 

37   

38 /* 建堆方法，只需线性时间建好； 

39    建堆的结果：数组的第一个元素（即树根）是所有元素中的最小值，索引小于等于size/2-1的其它元素（即其它非叶子节点）的值都是其所在子树的最小值 */   

40 void BuildHeap(int num[] ,int size) {  

41     int i;  

42     //从最后一个非叶子节点开始，对每个非叶子节点进型最小根调整，保证每个根节点都是其子树中的最小值 

43     for (i = size / 2 - 1; i >= 0; i--) {    

44         PercolateDown(num, i,size);// 进行下滤操作 

45         PrintHeap("Build heap:",num,size); 

46     }    

47 } 

48       

49 /* 对该数进行下滤操作，直到该数比左右节点都小就停止下滤。 

50    即对某个根节点的值进行位置下降调整，使该值比其左右子节点都小； 

51    若该节点是叶子节点，则无法while循环 */

52 void PercolateDown(int num[] , int index,int size) {    

53     int min;// 设置最小指向下标    

54     while (index * 2 + 1<size) {// 如果该数有左节点，则假设左节点最小    

55         min = index * 2 + 1;// 获取左节点的下标    

56         if (index * 2 + 2<size) {// 如果该数还有右节点    

57             if (num[min] > num[index * 2 + 2]) {// 就和左节点分出最小者    

58                 min = index * 2 + 2;// 此时右节点更小，则更新min的指向下标    

59             }    

60         }    

61         // 此时进行该数和最小者进行比较，    

62         if (num[index] < num[min]) {// 如果index最小，    

63             break;// 停止下滤操作    

64         } else {    

65             Swap(num, index, min);// 交换两个数，让大数往下沉    

66             index = min;// 更新index的指向    

67         }    

68     }// while    

69 } 

70       

71 // 给定数组交换两个数的位置    

72 void Swap(int num[] , int v, int u) {   

73     int temp = num[v];    

74     num[v] = num[u];    

75     num[u] = temp;    

76 }    

77   

78 void PrintHeap(const char* strMsg,int array[],int nLength) 

79 { 

80      int i; 

81      printf("%s",strMsg); 

82      for(i=0;i<nLength;i++) 

83      { 

84         printf("%d ",array[i]); 

85      } 

86      printf("\n"); 

87 }