基本思想
- 堆的定义
n个关键字序列kl,k2,…,kn称为堆,当且仅当该序列满足如下性质之一(简称堆性质):
- ki≤k2i且ki≤k2i+1 或
- ki≥k2i且ki≥k2i+1(1≤i≤FLOOR(n/2))
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若 存在)结点的关键字。
- 小根堆:根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小的。
- 大根堆:根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大的。
我们可以选择大根堆或者小根堆中的任意一个来进行排序。
- 排序思想
用大根堆排序的基本思想:
- 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区。
- 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得 到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key。
- 由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。 然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由 此得到新的无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系 R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。
算法实现
堆排序算法,Java实现,代码如下所示:
01 |
public abstract class Sorter { |
02 |
public abstract void sort( int [] array); |
03 |
} |
04 |
05 |
public class HeapSorter extends Sorter { |
06 |
07 |
public void sort( int [] array) { |
08 |
heapSort(array); |
09 |
} |
10 |
11 |
/** |
12 |
* <p>堆排序方法 |
13 |
* <p>基于大根堆的堆排序方法 |
14 |
*/ |
15 |
private void heapSort( int [] array) { |
16 |
Integer tmp; // 用于交换的暂存单元 |
17 |
buildHeap(array); // 执行初始建堆,并调整 |
18 |
for ( int i = 0 ; i < array.length; i++) { |
19 |
// 交换堆顶元素array[0]和堆中最后一个元素array[array.length-1-i] |
20 |
tmp = array[ 0 ]; |
21 |
array[ 0 ] = array[array.length - 1 - i]; |
22 |
array[array.length - 1 - i] = tmp; |
23 |
// 每次交换堆顶元素和堆中最后一个元素之后,都要对堆进行调整 |
24 |
adjustHeap(array, 0 , array.length - 1 - i); |
25 |
} |
26 |
} |
27 |
28 |
/** |
29 |
* <p> |
30 |
* 建堆方法 |
31 |
* <p> |
32 |
* 调整堆中0~array.length/2个结点,保持堆的性质 |
33 |
* |
34 |
*/ |
35 |
private void buildHeap( int [] array) { |
36 |
// 求出当前堆中最后一个存在孩子结点的索引 |
37 |
int pos = (array.length - 1 ) / 2 ; |
38 |
// 从该结点结点开始,执行建堆操作 |
39 |
for ( int i = pos; i >= 0 ; i--) { |
40 |
adjustHeap(array, i, array.length); // 在建堆过程中,及时调整堆中索引为i的结点 |
41 |
} |
42 |
} |
43 |
44 |
/** |
45 |
* <p> |
46 |
* 调整堆的方法 |
47 |
* |
48 |
* @param s 待调整结点的索引 |
49 |
* @param m 待调整堆的结点的数量(亦即:排除叶子结点) |
50 |
*/ |
51 |
private void adjustHeap( int [] array, int s, int m) { |
52 |
Integer tmp = array[s]; // 当前待调整的结点 |
53 |
int i = 2 * s + 1 ; // 当前待调整结点的左孩子结点的索引(i+1为当前调整结点的右孩子结点的索引) |
54 |
while (i < m) { |
55 |
if (i + 1 < m && array[i] < array[i + 1 ]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点) |
56 |
i = i + 1 ; |
57 |
} |
58 |
if (array[s] < array[i]) { |
59 |
array[s] = array[i]; // 孩子结点大于当前待调整结点,将孩子结点放到当前待调整结点的位置上 |
60 |
s = i; // 重新设置待调整的下一个结点的索引 |
61 |
i = 2 * s + 1 ; |
62 |
} else { // 如果当前待调整结点大于它的左右孩子,则不需要调整,直接退出 |
63 |
break ; |
64 |
} |
65 |
array[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上 |
66 |
} |
67 |
} |
68 |
} |
堆排序算法,Python实现,代码如下所示:
01 |
class Sorter: |
02 |
''' |
03 |
Abstract sorter class, which provides shared methods being used by |
04 |
subclasses. |
05 |
''' |
06 |
__metaclass__ = ABCMeta |
07 |
|
08 |
@abstractmethod |
09 |
def sort( self , array): |
10 |
pass |
11 |
12 |
class HeapSorter(Sorter): |
13 |
''' |
14 |
Heap sorter |
15 |
''' |
16 |
def sort( self , array): |
17 |
length = len (array) |
18 |
self .__heapify(array) |
19 |
i = 0 |
20 |
while i<length: |
21 |
array[ 0 ], array[length - 1 - i] = array[length - 1 - i], array[ 0 ] |
22 |
self .__sift_down(array, 0 , length - 1 - i) |
23 |
i = i + 1 |
24 |
|
25 |
def __heapify( self , array): |
26 |
length = len (array) |
27 |
pos = (length - 1 ) / / 2 |
28 |
i = pos |
29 |
while i> = 0 : |
30 |
self .__sift_down(array, i, length) |
31 |
i = i - 1 |
32 |
|
33 |
def __sift_down( self , array, s, m): |
34 |
tmp = array[s] |
35 |
i = 2 * s + 1 |
36 |
while i<m: |
37 |
if i + 1 <m and array[i]<array[i + 1 ]: |
38 |
i = i + 1 |
39 |
if array[s]<array[i]: |
40 |
array[s] = array[i] |
41 |
s = i |
42 |
i = 2 * s + 1 |
43 |
else : |
44 |
break |
45 |
array[s] = tmp |
排序过程
假设待排序数组为array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49},数组大小为20。
第一步:初始建堆
首先执行的初始建堆(在建堆的过程中需要调整堆)。过程如下:
- 求出当前堆中最后一个存在孩子结点的索引
这里,把数组array看做是一棵完全二叉树,这样数组每个索引位置上的元素都对应到二叉树中的结点,如图所示:
其中需要在这棵树中找到最后一个有孩子最大的一个结点的索引:
pos = (array.length-1)/2 = (20-1)/2 = 9
也就是索引为9的array[9] = 76,由后至前层次遍历,从array[9]一直到array[0],对初始堆进行调整。
- 对初始堆进行调整
- 调整结点array[9] = 76:
先比较array[9] = 76的左右孩子:s = 9,i = 2*s+1 = 2*9 + 1 = 19,而i+1 = 19 + 1 = 20 > m = array.length-1 = 20 -1 = 19(array[9] = 76没有右孩子),只需要将array[9] = 76与array[i] = array[19] = 49比较,因为array[9] = 76>array[i] = array[19] = 49,则不需要交换array[9] = 76与array[i] = array[19] = 49,继续对下一个结点(也就是array[8] = 55)进行调整;
调整结点array[8] = 55:先比较array[8] = 55的左右孩子:s = 8,i = 2*s+1 = 2*8 + 1 = 17,,而i+1 = 17 + 1 = 18 < m = array.length-1 = 20-1 = 19(array[8] = 55存在右孩子),左孩子array[i] = array[17] = 65小于右孩子array[i+1] = array[18] = 76,只需要将array[8] = 76与右孩子array[i+1] = array[18] = 76比较,因为array[8] = 55<array[i+1] = array[18] = 76,则需要交换array[8] = 55与array[i+1] = array[18] = 76,交换后如图所示:
继续对下一个结点(也就是array[8] = 55)进行调整; 调整结点array[7] = 37:
显然,不需要交换;
调整结点array[6] = 0:调整结果如图所示:
调整结果如图所示:
调整结果如图所示:
显然,不需要交换。
调整结点array[2] = 34:调整结果如图所示:
调整结果如图所示:
显然,不需要交换。
至此,对初始堆的调整完成。
第二步:第一次交换
将堆顶元素与最后一个元素交换,即array[0] = 94与最后一个元素array[19] = 49交换,如图所示:
此时,数组为:
array = {49,76,90,12,76,68,34,37,76,26,37,5,9,83,0,37,12,65,55,94}
数组中最大的元素被交换到了数组的末尾,也就是array[19] = 94是最终排好序的固定位置。
第三步:调整堆
过程同前面类似。
……
最后经过堆排序得到有序的数组。
算法分析
- 时间复杂度
堆排序的时间,主要由建立初始堆和反复重建堆这两部分的时间开销构成。
堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。
- 空间复杂度
堆排序过程中,需要调整堆,交换待排序记录需要一个临时存储单元,所以空间复杂度为O(1)。
- 排序稳定性
堆排序是就地排序,它是不稳定的排序方法。