堆排序

这里的堆特指二叉堆,它来自于优先队列。

堆的定义

当一颗二叉树的每个结点都大于等于它的两个子节点时,它被称为堆有序
二叉堆是一组能够用堆有序的完全二叉树排序的元素,并在数组中按照层级储存(不使用数组的第一个位置)

示例可以参考这里

堆的性质(数组存储方法)

  1. 由于根节点规定在位置1,所以,位置k的结点的父节点位置即为k/2的向下取整
  2. 位置k的结点的两个子节点位置则分别位2k和2k+1

堆算法

在堆的有序化上有两种操作:

  1. 当某个结点的优先级上升(或是在堆低加入一个新的元素)时,需要由下至上恢复堆的顺序。(swim)
  2. 当某个结点的优先级下降(例如:将根节点替换为一个较小的元素)时,需要由上至下恢复堆的顺序。(sink)

由下至上有序化堆(上浮)

如果堆的有序状态因为某个结点变得比它的父节点更大而被破坏,那么我们就需要通过交换它和它的父节点来修复堆;但交换后的这个结点仍然可能比它现在的父节点大,所以我们需要用同样的方法一遍遍恢复堆的秩序。

代码实现:

1
2
3
4
5
6
7
8
void swim(int k)
{
while(k>1 && less(k/2, k))
{
exch(k/2, k);
k = k/2;
}
}

swim()方法中的循环可以保证只有堆的有序状态在位置k处被打破(位置k上的结点大于它的父节点)时才会执行,所以只要该节点不再大于它的父节点,堆的有序状态就恢复了。

由上至下有序化堆(下沉)

如果堆的有序状态因为某个结点变得比它的两个子节点或是其中之一更小了而被打破了,那么我们可以通过将它和它的两个子节点中的较大者交换来恢复堆。交换可能会在子节点处继续打破堆的有序状态,因此我们需要不断的用相同的方法将其修复,将结点向下移动直到得到它的子节点都比它更小或是达到了堆的底部。

代码实现:

1
2
3
4
5
6
7
8
9
10
11
void sink(int a[], int k, int N)
{
while(2*k <= N)
{
int j = 2*k;
if( j<N && less(j, j+1)) j++;
if(!less(k, j)) break;
exch(k, j);
k = j;
}
}

插入与删除

有了上面两种对堆的最基本操作就可以构建很多堆的基本算法。

插入:可以将新元素加到数组末尾,增加堆的大小并让新元素上浮到合适的位置。
删除最大元素:可以从数组顶端删去最大的元素并将数组的最后一个元素放到顶端,减小堆的大小并让这个元素下沉到合适的位置。

堆排序

我们可以把任意优先队列变成一种排序算法。
将所有元素插入一个查找最小元素的优先队列,然后再重复调用删除最小元素的操作来将它们按顺序删去,则删去的序列即为排序后的序列(这里和之前的分析保持一致,采用面向最大元素的优先队列并重复删除最大元素)。

堆排序可以分为两个阶段:

  1. 构建堆:将原始数组重新组织安排进一个堆中。
  2. 下沉:从堆中按照递减顺序取出所有元素并得到排序结果。

堆的构建

两种方法:

  1. 从左向右遍历数组,用swim()保证扫描指针左侧的所有元素已经是一颗堆有序的完全数,就像连续向优先队列中插入元素一样。【O(NlogN)】
  2. 从右向左用sink()函数构造子堆,数组的每个位置都已经是一个子堆的根节点,sink()对于这些子堆也使用。如果一个结点的两个子节点都已经是堆了,那么在该节点上调用sink()可以将它们变成一个堆,这个过程会递归地建立起堆的秩序。【2N次比较,N次交换】

    开始时只需要扫描数组中的一半元素,因为我们可以跳过大小为1的子堆,最后在位置1上调用sink()方法,扫描结束。

明显第二种方法更优秀,下面介绍第二种方法。

堆有序举例:

N k a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11]
0x53 0x4F 0x52 0x54 0x45 0x58 0x41 0x4D 0x50 0x4C 0x45
11 5 0x4C 0x45
11 4 0x54
11 3 0x58 0x52
11 2 0x54 0x50 0x4F
11 1 0x58 0x53
堆有序 0x58 0x54 0x53 0x50 0x4C 0x52 0x41 0x4D 0x4F 0x45 0x45

注意:堆有序只是说任意位置k的数都大于等于位置2k和位置2k+1的数,并不代表所有数有序。

代码:

1
2
3
4
for(int k=N/2; k>=1; k--)
{
sink(a, k, N);
}

下沉排序

排序工作主要是在这里完成的:删除最大元素,然后放入堆缩小后数组空出的位置。这个过程和选择排序有些类似,但所需的比较要少得多,因为堆提供了一种从未排序部分找到最大元素的有效方法。

接着上面堆有序的结果:

N k a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] a[11]
0x58 0x54 0x53 0x50 0x4C 0x52 0x41 0x4D 0x4F 0x45 0x45
11 1 0x45 0x58
10 1 0x54 0x45 0x58
10 1 0x50 0x45 0x58
10 1 0x4F 0x45 0x58
10 1 0x45 0x54 0x58
9 1 0x53 0x45 0x54 0x58
9 1 0x52 0x45 0x54 0x58
9 1 0x45 0x53 0x54 0x58
8 1 0x52 0x45 0x53 0x54 0x58
8 1 0x4D 0x52 0x53 0x54 0x58
7 1 0x50 0x4D 0x52 0x53 0x54 0x58
7 1 0x4F 0x4D 0x52 0x53 0x54 0x58
7 1 0x41 0x50 0x52 0x53 0x54 0x58
6 1 0x4F 0x41 0x50 0x52 0x53 0x54 0x58
6 1 0x4D 0x41 0x50 0x52 0x53 0x54 0x58
6 1 0x45 0x4F 0x50 0x52 0x53 0x54 0x58
5 1 0x4D 0x45 0x4F 0x50 0x52 0x53 0x54 0x58
5 1 0x4C 0x45 0x4F 0x50 0x52 0x53 0x54 0x58
5 1 0x45 0x4D 0x4F 0x50 0x52 0x53 0x54 0x58
4 1 0x4C 0x45 0x4D 0x4F 0x50 0x52 0x53 0x54 0x58
4 1 0x41 0x4C 0x4D 0x4F 0x50 0x52 0x53 0x54 0x58
3 1 0x45 0x41 0x4C 0x4D 0x4F 0x50 0x52 0x53 0x54 0x58
3 1 0x45 0x45 0x4C 0x4D 0x4F 0x50 0x52 0x53 0x54 0x58
2 1 0x41 0x45 0x45 0x4C 0x4D 0x4F 0x50 0x52 0x53 0x54 0x58
1 1 0x41 0x45 0x45 0x4C 0x4D 0x4F 0x50 0x52 0x53 0x54 0x58

排序完成

代码:

1
2
3
4
5
while(N > 1)
{
exch(a, 1, N--);
sink(a, 1, N);
}

完整的堆排序程序

需要修改为模板函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void exch(a, k, N)
{
int tmp = a[N];
a[N] = a[k];
a[k] = tmp;
}

void sink(int a[], int k, int N)
{
while(2*k <= N)
{
int j = 2*k;
if( j<N && less(j, j+1)) j++;
if(!less(k, j)) break;
exch(k, j);
k = j;
}
}

void sort(int a)
{
int N = a.size();
for(int k=N/2; k>=1; k--){
sink(a, k, N);
}
while(N > 1){
exch(a, 1, N--);
sink(a, 1, N);
}
}
Brick wechat
扫一扫,用手机看更方便(^ ◕ᴥ◕ ^)