版本记录

前言

简单介绍堆排序 - heapsort

堆排序也是我们常用的一种算法，它像合并排序不像插入排序，堆排序的运行时间为O(nlgn)，它是一种原地（in place）排序算法，在任何时候，数组中只有常数个元素存储在输入数组外。

堆

二叉堆数据结构是一种数组现象，如下图所示。树中的每个节点与数组中存放该节点值的那个元素对应。

上面这个数据结构可以这么理解：

• a是一颗二叉树，b是一个数组
• 圆圈中的数字表示树中每个节点存储的值，节点上方的数字表示对应的数组下标，数字上下的连线表示父子关系，其父节点总在子节点的左边。
• 树的高度为3，存储值为8的4号节点的高度为1

这里父子节点满足下面的关系。

这里节点的 2i 和 2i + 1 都可以通过二进制的移位获取。

二叉堆有两种：最大堆和最小堆，在最大堆中，最大堆特性是指除了根以外的每个节点i，都有：

A[PARENT(i)] ≥ A[i]

即某个节点的值至多是和其父节点的值一样大，这样堆中的最大元素就存放在根节点中，在以某一个结点为根的子树中，各结点的值都不大于该子树根节点的值。

最小堆则刚好相反，最小堆特性是指除了根以外的每个结点i，都有：

A[PARENT(i)] ≤ A[i]

也就是说最小堆的最小元素是在根部的，在堆排序算法中，我们使用的是最大堆，最小堆一般是在构造优先队列时使用。

具有n个元素的堆是基于一棵完全二叉树的，高度为Θ(lgn)。下面出五个基本过程，并说明他们在排序算法和优先级队列数据结构中如何使用。

• MAX - HEAPIFY过程，运行时间为O(lgn)，是保持最大堆性质的关键。
• BUILD - MAX - HEAP过程，以线性时间运行，可以在无序的输入数组基础上构造出最大堆。
• HEAPSORT过程，运行时间为O(nlgn)，对一个数组原地进行排序。
• MAX - HEAP - INSERT, HEAP - EXTRACT - MAX, HEAP - INCREASE - KEY 和 HEAP - MAXIMUM过程的运行时间为O(lgn)，可以让堆结构作为优先队列使用。

堆性质的保持

MAX - HEAPIFY是对最大堆进行操作的重要的子程序，其输入为一个数组A和下标i。

下面看一下伪代码。

下面看一下详细的过程。

• 在算法的每一步里面，从元素A[ i ], A[LEFT(i)], A[RIGHT(i)]中找到最大的并将下标存在largest中。
• 如果A[ i ]是最大的，那么以i为根的子树已是最大堆，程序结束；否则，i 的某个结点中有最大元素，则交换A[ i ]和A[largest]，从而使i及其子女满足堆性质，下标为largest的结点在交换后的值是A[ i ]，以该结点为根的子树有可能违反最大堆性质，因而要对该子树递归调用MAX - HEAPIFY。

当heap - size[A] = 10时，MAX - HEAPIFY (A, 2)的作用过程如下：

• a)初始构造，在结点 i = 2处， A[ 2 ]违反了最大堆性质，因为它不大于它的两个子女。
• b)变换A[2]与A[4]，在结点2处恢复了最大堆性质，但又在结点4处违反了最大堆性质，现在递归调用MAX - HEAPIFY(A, 4)，置 i = 4。
• c)中交换了A[ 4 ] 和 A[ 9 ]，结点4的最大堆性质得到恢复，递归调用MAX - HEAPIFY(A, 9)对给数据结构不会再引起任何变化。

MAX - HEAPIFY运行时间

下面我们就看一下运行时间。

当MAX - HEAPIFY作用在一棵以结点i为根的，大小为n的子树上时，其运行时间为调整元素A[ i ]、A[LEFT( i )]和A[RIGHT( i )]的关系所用时间Θ(1)，再加上对以i的某个结点为根的子树递归调用MAX - HEAPIFY所需的时间，i结点的子树大小最多为2n / 3，最坏情况就是最底层恰好半满的时候，下面看一下表达式：

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

这个递归式的解为 T( n ) = O(lgn)，或者说MAX - HEAPIFY作用于一个高度为h的结点所需运行时间为O(h)。

后记

未完，待续~~~