一 : 堆排序及算法分析

堆排序及算法分析

前言

记得在学习数据结构的时候一味的想用代码实现算法，重视的是写出来的代码有一个正确的输入，然后有一个正确的输出，那么就很满足了。（www.61k.com]从网上看了许多的代码，看了之后貌似懂了，自己写完之后也正确了，但是不久之后就忘了，因为大脑在回忆的时候，只依稀记得代码中的部分，那么的模糊，根本不能再次写出正确的代码，也许在第一次写的时候是因为参考了别人的代码，看过之后大脑可以进行短暂的高清晰记忆，于是欺骗了我，以为自己写出来的，满足了成就感。可是代码是计算机识别的，而我们更喜欢文字，图像。所以我们在学习算法的时候要注重算法的原理以及算法的分析，用文字，图像表达出来，然后当需要用的时候再将文字转换为代码。记忆分为三个步骤：编码，存储和检索，就以学习为例，先理解知识，再归纳知识，最后巩固知识，为了以后的应用而方便检索知识。

堆排序过程

堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

既然是堆排序，自然需要先建立一个堆，而建堆的核心内容是调整堆，使二叉树满足堆的定义（每个节点的值都不大于其父节点的值）。调堆的过程应该从最后一个非叶子节点开始，假设有数组A = {1, 3, 4, 5, 7, 2, 6, 8, 0}。那么调堆的过程如下图，数组下标从0开始，A[3] = 5开始。分别与左孩子和右孩子比较大小，如果A[3]最大，则不用调整，否则和孩子中的值最大的一个交换位置，在图1中是A[7] > A[3] > A[8]，所以A[3]与A[7]对换，从图1.1转到图1.2。

堆排序算法 堆排序及算法分析

所以建堆的过程就是

1: for ( i = headLen/2; i >= 0; i++)

2:

3: do AdjustHeap(A, heapLen, i)

调堆：如果初始数组是非降序排序，那么就不需要调堆，直接就满足堆的定义，此为最好情况，运行时间为Θ(1)；如果初始数组是如图1.5，只有A[0] = 1不满足堆的定义，经过与子节点的比较调整到图1.6，但是图1.6仍然不满足堆的定义，所以要递归调整，一直到满足堆的定义或者到堆底为止。（www.61k.com]如果递归调堆到堆底才结束，那么是最坏情况，运行时间为O(h) (h为需要调整的节点的高度，堆底高度为0，堆顶高度为floor(logn) )。

建堆完成之后，堆如图1.7是个大根堆。将A[0] = 8 与 A[heapLen-1]交换,然后heapLen减一，如图2.1，然后AdjustHeap(A, heapLen-1, 0)，如图2.2。如此交换堆的第一个元 素和堆的最后一个元素，然后堆的大小heapLen减一，对堆的大小为heapLen的堆进行调堆，如此循环，直到heapLen == 1时停止，最后得出结果如图3。

堆排序算法 堆排序及算法分析

17: largest = left;

堆排序算法 堆排序及算法分析

18: }

19:

20: if (right < hLen && A[largest] < A[right])

21: {

22: largest = right;

23: }

24:

25: if (i != largest) //如果最大值不是父节点

26: {

27: temp = A[largest]; //交换父节点和和拥有最大值的子节点交换

28: A[largest] = A[i];

29: A[i] = temp;

30:

31: i = largest; //新的父节点，以备迭代调堆 32: left = LeftChild(i); //新的子节点

33: right = RightChild(i);

34: }

35: else

36: {

37: break;

38: }

39: }

40: }

41:

42: /*

43: 输入：数组A，堆的大小hLen

44: 功能：建堆

45: */

46: void BuildHeap(int A[], int hLen)

47: {

48: int i;

49: int begin = hLen/2 - 1; //最后一个非叶子节点

50: for (i = begin; i >= 0; i--)

51: {

堆排序算法 堆排序及算法分析

52: AdjustHeap(A, hLen, i);

53: }

54: }

55:

56: /*

57: 输入：数组A，待排序数组的大小aLen

58: 功能：堆排序

59: */

60: void HeapSort(int A[], int aLen)

61: {

62: int hLen = aLen;

63: int temp;

64:

65: BuildHeap(A, hLen); //建堆

66:

67: while (hLen > 1)

68: {

69: temp = A[hLen-1]; //交换堆的第一个元素和堆的最后一个元素

70: A[hLen-1] = A[0];

71: A[0] = temp;

72: hLen--; //堆的大小减一

73: AdjustHeap(A, hLen, 0); //调堆

74: }

75: }

性能分析

?

? 调堆：上面已经分析了，调堆的运行时间为O(h)。［www.61k.com) 建堆：每一层最多的节点个数为n1 = ceil(n/(2^(h+1))),

堆排序算法 堆排序及算法分析

因此，建堆的运行时间是O(n)。（www.61k.com] ? 循环调堆（代码67-74），因为需要调堆的是堆顶元素，所以运行时间是O(h) =

O(floor(logn))。所以循环调堆的运行时间为O(nlogn)。 总运行时间T(n) = O(nlogn) + O(n) = O(nlogn)。对于堆排序的最好情况与最坏情况的运行时间，因为最坏与最好的输入都只是影响建堆的运行时间O(1)或者O(n)，而在总体时间中占重要比例的是循环调堆的过程，即O(nlogn) + O(1) =O(nlogn) + O(n) = O(nlogn)。因此最好或者最坏情况下，堆排序的运行时间都是O(nlogn)。而且堆排序还是原地算法（in-place 。

61阅读提醒您本文地址：

结尾

如果不太了解O,Θ等渐进符号的，可以参考博文:计算机算法分析之渐进记号。 上述文章是我的学习笔记，如有错误，还望不吝赐教。

61阅读提醒您本文地址：

二 : 堆排序算法伪代码

// 草稿，待完善/////////////////////////////////////////////////////void HeapSort( 数组，元素个数){BuildHeap( 数组，堆大小); // 大小就是包含的元素个数 for(堆元素总个数减一 次循环 ) {将“堆顶”元素同“堆底”元素交换；// 第一个和最后一个RebuildHeap(数组，堆大小减一);//每次都会筛选出一个最大（最小）的元素 } //循环结束后，数组就是有序的}void BuildHeap( 数组，堆大小){ i = 1; for(堆大小减一 次循环 ) {当前节点为数组第 i++ 个元素 ；while( 当前节点值 大于 其父节点值 ){当前节点的父节点作为新的当前节点（注意同时交换数据）；if( 当前节点是堆顶 ) break;} }}void RebuildHeap(数组，堆大小){当前节点为堆顶; // 即第一个元素（下标是0）while(1) {if( 当前节点无左子节点) break; //已经到堆底if( 当前节点无右子节点 ){if( 当前节点元素小于左子节点) 当前节点同左子节点交换；break; // 说明当前节点为次地层}确定当前节点、左子节点、右子节点中元素数据最大的一个；if(最大的不是当前节点 ){较大的节点同当前节点交换;较大的节点作为新的当前节点;continue;}break; // 当前节点最大，说明当前位置正合适。 }}/////////////////////////////////////////////////////////

三 : 堆排序算法普及教程

本文参考：Introduction To Algorithms，second edition。

本文我们要讲的是堆排序算法。据我所知，要真正彻底认识一个算法，最好是去查找此算法的原发明者的论文或相关文献。

ok，此节，咱们开始吧。

一、堆排序算法的基本特性

时间复杂度：O(nlgn)...

//等同于归并排序

最坏：O(nlgn)

空间复杂度：O(1).

不稳定。

二、堆与最大堆的建立

要介绍堆排序算法，咱们得先从介绍堆开始，然后到建立最大堆，最后才讲到堆排序算法。

2.1、堆的介绍

如下图，

a），就是一个堆，它可以被视为一棵完全二叉树。

每个堆对应于一个数组b），假设一个堆的数组A，

我们用length[A]表述数组中的元素个数，heap-size[A]表示本身存放在A中的堆的元素个数。

当然，就有，heap-size[A]<=length[A]。

树的根为A[1]，i表示某一结点的下标，

则父结点为PARENT(i)，左儿子LEFT[i]，右儿子RIGHT[i]的关系如下：

PARENT(i)

return |_i/2_|

LEFT(i)

return 2i

RIGHT(i)

return 2i + 1

二叉堆根据根结点与其子结点的大小比较关系，分为最大堆和最小堆。

最大堆：

根以外的每个结点i都不大于其根结点，即根为最大元素，在顶端，有

A[PARENT(i)] （根）≥ A[i] ,

最小堆：

根以外的每个结点i都不小于其根结点，即根为最小元素，在顶端，有

A[PARENT(i)] （根）≤ A[i] .

在本节的堆排序算法中，我们采用的是最大堆；最小堆，通常在构造最小优先队列时使用。

由前面，可知，堆可以看成一棵树，所以，堆的高度，即为树的高度，O(lgn)。

所以，一般的操作，运行时间都是为O(lgn)。

具体，如下：

The MAX-HEAPIFY：O(lgn) 这是保持最大堆的关键.

The BUILD-MAX-HEAP:线性时间。在无序输入数组基础上构造最大堆。

The HEAPSORT：O(nlgn) time, 堆排序算法是对一个数组原地进行排序.

The MAX-HEAP-INSERT, HEAP-EXTRACT-MAX, HEAP-INCREASE-KEY, HEAP-MAXIMUM：O(lgn)。

可以让堆作为最小优先队列使用。

2.2.1、保持堆的性质(O（lgn）)

为了保持最大堆的性质，我们运用MAX-HEAPIFY操作，作调整，递归调用此操作，使i为根的子树成为最大堆。

MAX-HEAPIFY算法，如下所示（核心）：

MAX-HEAPIFY(A,i)
l←LEFT(i)
r←RIGHT(i)
ifl≤heap-size[A]andA[l]>A[i]
thenlargest←l
elselargest←i
ifr≤heap-size[A]andA[r]>A[largest]
thenlargest←r
iflargest≠i
thenexchangeA[i]<->A[largest]
MAX-HEAPIFY(A,largest)

如上，首先第一步，在对应的数组元素A[i], 左孩子A[LEFT(i)], 和右孩子A[RIGHT(i)] 中找到最大的那一个，将其下标存储在largest中。如果A[i]已经就是最大的元素，则程序直接结束。否则，i的某个子结点为最大的元素，将其，即 A[largest]与A[i]交换，从而使i及其子女都能满足最大堆性质。下标largest所指的元素变成了A[i]的值，会违反最大堆性质，所以对 largest所指元素调用MAX-HEAPIFY。如下，是此MAX-HEAPIFY的演示过程（下图是把4调整到最底层，一趟操作，但摸索的时间为LogN）：

由上图，我们很容易看出，初始构造出一最大堆之后，在元素A[i]，即16， 大于它的俩个子结点4、10，满足最大堆性质。所以，i下调指向着4,小于,左子14，所以，调用MAX-HEAPIFY，4与其子，14交换位置。但4 处在了14原来的位置之后，4小于其右子8，又违反了最大堆的性质，所以再递归调用MAX-HEAPIFY，将4与8，交换位置。于是，满足了最大堆性 质，程序结束。

2.2.2、MAX-HEAPIFY的运行时间

MAX-HEAPIFY作用在一棵以结点i为根的、大小为n的子树上时，其运行时间为调整元素A[i]、A[LEFT(i)]，A[RIGHT(i)]的 关系时所用时间为O(1)，再加上，对以i的某个子结点为根的子树调用MAX-HEAPIFY所需的时间，且i结点的子树大小至多为2n/3，所 以，MAX-HEAPIFY的运行时间为

T (n) ≤ T(2n/3) + Θ(1).

我们，可以证得此式子的递归解为T(n)=O(lgn)。具体证法，可参考算法导论第6章之6.2节，这里，略过。

2.3.1、建堆(O（N）)

BUILD-MAX-HEAP(A)

heap-size[A]←length[A]
fori←|_length[A]/2_|downto1
doMAX-HEAPIFY(A,i)//建堆，怎么建列?原来就是不断的调用MAX-HEAPIFY(A,i)来建立最大堆。

BUILD-MAX-HEAP通过对每一个其它结点，都调用一次MAX-HEAPIFY，

来建立一个与数组A[1...n]相对应的最大堆。A[(|_n/2_|+1) ‥ n]中的元素都是树中的叶子。

因此，自然而然，每个结点，都可以看作一个只含一个元素的堆。

关于此过程BUILD-MAX-HEAP(A)的正确性，可参考算法导论 第6章之6.3节。

下图，是一个此过程的例子（下图是不断的调用MAX-HEAPIFY操作，把所有的违反堆性质的数都要调整，共N趟操作，然，摸索时间最终精确为O（N））：

2.3.2、BUILD-MAX-HEAP的运行时间

因为每次调用MAX-HEAPPIFY的时间为O(lgn)，而共有O(n)次调用，所以BUILD-MAX-HEAP的简单上界为O(nlgn)。算法导论一书提到，尽管这个时间界是对的，但从渐进意义上，还不够精确。

那么，更精确的时间界，是多少列?

由于，MAX-HEAPIFY在树中不同高度的结点处运行的时间不同，且大部分结点的高度都比较小，

而我们知道，一n个元素的堆的高度为|_lgn_|(向下取整)，且在任意高度h上，至多有|-n/2^h+1-|(向上取整)个结点。

因此，MAX-HEAPIFY作用在高度为h的结点上的时间为O(h)，所以，BUILD-MAX-HEAP的上界为：O（n）。具体推导过程，略。

三、堆排序算法

所谓的堆排序，就是调用上述俩个过程：一个建堆的操作、BUILD-MAX-HEAP，一个保持最大堆的操作、MAX-HEAPIFY。详细算法如下：

HEAPSORT(A) //n-1次调用MAX-HEAPIFY，所以，O（n*lgn）

BUILD-MAX-HEAP(A)//建最大堆，O（n）
fori←length[A]downto2
doexchangeA[1]<->A[i]
heap-size[A]←heap-size[A]-1
MAX-HEAPIFY(A,1)//保持堆的性质，O（lgn）

如上，即是堆排序算法的完整表述。下面，再贴一下上述堆排序算法中的俩个建堆、与保持最大堆操作：

BUILD-MAX-HEAP(A)//建堆
heap-size[A]←length[A]
fori←|_length[A]/2_|downto1
doMAX-HEAPIFY(A,i)
MAX-HEAPIFY(A,i)//保持最大堆
l←LEFT(i)
r←RIGHT(i)
ifl≤heap-size[A]andA[l]>A[i]
thenlargest←l
elselargest←i
ifr≤heap-size[A]andA[r]>A[largest]
thenlargest←r
iflargest≠i
thenexchangeA[i]<->A[largest]
MAX-HEAPIFY(A,largest)

以下是，堆排序算法的演示过程（通过，顶端最大的元素与最后一个元素不断的交换，交换后又不断的调用MAX-HEAPIFY以重新维持最大堆的性质，最后，一个一个的，从大到小的，把堆中的所有元素都清理掉，也就形成了一个有序的序列。这就是堆排序的全部过程。）：

上图中，a->b，b->c，....之间，都有一个顶端最大元素与最小元素交换后，调用MAX-HEAPIFY的过程，我们知道，此MAX-HEAPIFY的运行时间为O（lgn），而要完成整个堆排序的过程，共要经过O（n）次这样的MAX-HEAPIFY操作。所以，才有堆排序算法的运行时间为O（n*lgn）。

后续：把堆想象成为一种树，二叉树之类的。所以，用堆做数据查找、删除的时间复杂度皆为O（logN）。 那么是一种什么样的二叉树列?一种特殊的二叉树，分为最大堆，最小堆。最大堆，就是上头大，下头小。最小堆就是上头小，下头大。

作者：July

本文标题：堆排序算法-堆排序及算法分析
本文地址： http://www.61k.com/1137440.html