算法4 优先队列和堆排序

优先队列(priority queue)区别于普通队列,在优先队列中,元素被赋予优先级。当访问元素时,拥有最高优先级的元素最先被删除。优先队列数据结构中主要的两个操作是插入元素和删除最大或最小元素。它的API如下:

各实现方案分析:

implementation insert del max max
unordered array 1 N N
ordered array N 1 1
goal log N log N log N

说明:关于有序数组的实现方式插入是N的原因,如果使用2分查找能在log N的时间内找到插入位置,但是插入元素需要移动数组,成本比较高。

无论是无序还是有序的数组实现优先队列都不适合处理大型问题,整体的时间成本是平方级别的。通常优先队列都使用二叉堆实现,他能保证每次插入和删除操作在log N的时间内。

优先队列(堆实现)

二叉堆是近似一棵完全二叉树,除了最下层的叶子节点,树是完美平衡的。

且不同于一般使用链表实现的二叉树,二叉堆因其特性可以使用数组实现,通常使用数组实现的数据结构在性能和

内存方面更有优势。

二叉堆有以下特性:

  • 根节点是最大元素,父节点不小于子节点;这种状态称为堆有序
  • 节点直接没有实际上的连接,而是通过少量的计算来确定父子关系。
  • 索引从1开始,不使用索引0
  • k的父节点在k/2的位置
  • k的子节点在2k2k+1的位置

二叉堆不使用数组索引0有两个原因:

  • k=0时,无法通过简单计算 k/22k2k+1,从而产生额外的判断。
  • 元素存储于1..N中,数组长度至少为N+1,所以最后一个元素k = N时角标不会越界,从而减少额外的判断。

上浮

当存在子节点大于父节点的情况时,需要执行上浮操作,让元素回到正确位置。

1
2
3
4
5
6
7
private void swim(int k) {
// k/2 表示父节点
while(k > 1 && less(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}

往二叉堆中插入元素时,可以将元素插入至末尾,然后对元素执行上浮操作。

1
2
3
4
public void insert(Key x) {
pq[++N] = x;
swim(N);
}

下沉

当存在父节点小于父节点的情况时,需要执行上浮操作,让元素回到正确位置。

1
2
3
4
5
6
7
8
9
10
11
private void sink(int k) {
// 2*k 2*k+1 表示k的两个子节点
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
3
4
5
6
7
public Key delMax() {
Key max = pq[1];
exch(1, N--);
sink(1);
pq[N+1] = null;
return max;
}

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class MaxPQ<Key extends Comparable<Key>> {
private Key[] pq;
private int N;

public MaxPQ(int capacity) {
// 数组最小长度为 N + 1
pq = (KEY[]) new Comparable[capacity+1];
}

public boolean isEmpty() {
return N == 0;
}

// 看前文的代码
public void insert() {}
public Key delMax() {}
private void swim(int k) {}
private void sink(int k) {}
private boolean less(int i, int j)
private void exch(int i, int j)
}

此优先队列构造中传入了容量,实际上应该自动扩增和缩减数组长度,这些在之前的文章中都有,不重复记录。

分析

二叉堆是一棵堆有序的完全二叉树,一棵大小为N的完全二叉树的高度为lgN。所以插入元素操作最多只需要lgN + 1次比较,而删除最大元素操作最多只需要2lgN次比较(一次用来找出最大子节点,一次用来确定该节点是否上浮)。

堆排序

二叉堆的数据结构也可用于对数组排序。使用堆排序主要有两个步骤:

  1. 通过下浮操作将数组构造成二叉堆
  2. 通过下沉操作排序

构造堆

长度为3的数组,只需一次下沉根节点的操作即可构造成堆。而对于更大的数组,只要遍历所有根节点(这里拥有叶子节点的节点)并执行下沉操作即可将数组构造成堆。

对于长度为N的数组,其最后的根节点为N/2,即数组前半部分的元素都属于根节点。所以将任意顺序的数组的前一半元素进行下沉操作,即可将数组变为堆有序,即二叉堆。

下沉排序

下沉排序的过程和选择排序非常相似,在选择排序中,总是遍历查找最大的一个元素放到数组的末尾。

下沉排序也是如此,但是二叉堆不需要遍历即可知道最大元素,因为那它的根节点。操作步骤如下:

  • 将根节点与最后一个元素交换,二叉堆长度减少1。
  • 此时二叉堆根节点不是最大元素,执行下沉操作。
  • 重复以上两个步骤直到排序完成

实现

现在有一个问题,因为二叉堆默认以索引1开始,而排序数组需要从0开始排序,如何解决?

这里有个非常简单的处理方式——角标映射。

1
2
3
binary heap's k: x 1 2 3 4 5 6
/ / / / / /
array's index: 0 1 2 3 4 5

要做到这种映射关系,只需要在访问数组时将索引减 1 即可,具体代码看下面的lessexch方法。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Heap {

public static void sort(Comparable[] pq) {
int n = pq.length;

// 构造堆
for (int k = n / 2; k >= 1; k--)
sink(pq, k, n);

// 堆排序
int k = n;
while (k > 1) {
exch(pq, 1, k--);
sink(pq, 1, k);
}
}

private static void sink(Comparable[] pq, int k, int n) {
while (2 * k <= n) {
int j = 2 * k;
if (j < n && less(pq, j, j + 1)) j++;
if (!less(pq, k, j)) break;
exch(pq, k, j);
k = j;
}
}

// 因为二叉堆索引从1开始,所以访问数组时需要将索引-1.
private static boolean less(Comparable[] pq, int i, int j) {
return pq[i - 1].compareTo(pq[j - 1]) < 0;
}

private static void exch(Comparable[] pq, int i, int j) {
Comparable temp = pq[i - 1];
pq[i - 1] = pq[j - 1];
pq[j - 1] = temp;
}

public static void main(String[] args) {
Integer[] a = Arrays.stream(StdRandom.permutation(9)).boxed().toArray(Integer[]::new);
StdOut.println("before:" + Arrays.toString(a));
Heap.sort(a);
StdOut.println(" after:" + Arrays.toString(a));
}
}

output:

1
2
before:[7, 8, 3, 1, 4, 6, 2, 0, 5]
after:[0, 1, 2, 3, 4, 5, 6, 7, 8]

分析

官方:https://algs4.cs.princeton.edu/24pq/

细节补充:https://alg4.ikesnowy.com/2-4-20/

如上图所示:

  • 一棵完全二叉树的高度为 h ;则节点的总量为 (等比数列和)
  • 下沉一个高度为 k 的节点时最多需要交换 k 次数组;
  • 高度为k的节点一共有,即高度为k的节点总交换次数最多为;

所以总的交换次数最多为:(总的比较次数为交换次数的两倍)

注:第等式的第三行中,第一项为等比数列和,可由公式直接求得;第二项为等差数列和与等比数列和之积,可由错位相减法求得。

将长度为N的数组构造成堆只需少于2N次比较(交换的两倍)和N次交换;

每次下沉操作最多需要2lgN次比较,即下沉N个元素的排序最多需要2NlgN次比较;

所以将N个元素排序,堆排序只需要少于2NlgN + 2N次比较(和一半次数的交换)

说明

很容易可以看出堆排序并不是稳定的排序,但值得关注的是堆排序是我们学过的算法中唯一能在最坏情况下保持NlgN级别性能的原地排序算法.

  • 归并排序:最坏情况下NlgN,非原地排序
  • 快速排序:最坏情况下N^2,原地排序
  • 堆排序:最坏情况下NlgN,原地排序

但是这并不是能让我们选择堆排序的理由,因为通常情况下快速排序性能更优。

算法总结

tight code:大意是紧凑且高效的代码。

至今仍然没有一种能够在NlgN比例的时间内原地且稳定的排序算法,有一些改进的归并排序算法非常接近这个要求,但是过于复杂,难以应用。

也没有任何一种算法能够适用于全部情况,每个排序算法都有各自的优点,需要结合实际情况选择最适合的排序。例如在元素基本有序的情况下,插入排序和冒泡排序仍然是最快的。

不过大多数情况下,需要保持稳定性时选择归并排序,否则选择快速排序,java的Arrays.sort()就是这么做的。