算法简单学习（八）—— 堆排序
版本记录
| 版本号 | 时间 |
|---|---|
| V1.0 | 2017.08.16 |
前言
将数据结构和算法比作计算机的基石毫不为过，追求程序的高效是每一个软件工程师的梦想。下面就是我对算法方面的基础知识理论与实践的总结。感兴趣的可以看上面几篇。
1. 算法简单学习（一）—— 前言
2. 算法简单学习（二）—— 一个简单的插入排序
3. 算法简单学习（三）—— 分治法与合并排序
4. 算法简单学习（四）—— 冒泡排序
5. 算法简单学习（五）—— 函数的增长
6. 算法简单学习（六）—— 常用的几种相关函数
7. 算法简单学习（七）—— 递归式
简单介绍堆排序 - 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)。
后记
未完，待续~~~
秋天
