0%

优先队列和堆排序

1. 介绍

优先队列是一种类似队列的数据结构,但是支持删除最大或最小元素以及插入元素

最重要的一点是,优先队列能存储很大的数据量,或者当你的内存很小的时候进行一些队列的操作

2. 基本实现

  1. 数组实现(无序)

    当次序不重要的时候,我们可以重用这一数据结构。
    insert() 方法就类似push() 方法
    对于 deleteMax() 方法,我们可以采用将最大的元素交换到栈顶的方法实现

  2. 数组实现(有序)

    当需要次序的时候,我们使用数组用于保持元素的次序
    为了维持这一次序,我们可以在插入的是偶将大的元素往右移动,这样,整个数组就会都是有序的。
    这时,我们只需要简单的调用 pop() 方法即可实现删除最大元素

  3. 链表实现

    由于上面使用了队列这几种数据结构,我们可以使用更高效的链表来实现他们。
    具体的算法思想和数组实现一致。

3. 二叉堆实现

3.1 二叉堆的定义

二叉堆是一个满足堆有序完全二叉树

堆有序:当所有的二叉树节点都大于或等于他们的两个子节点时,称二叉树堆有序

推论:二叉堆的根节点比任何节点都要大

3.2 二叉堆的表示法

因为二叉堆是一个完全二叉树

所以,我们可以轻松的使用数组来表示一个二叉堆。

即,当前节点为 k,则左子节点为 2k,右子节点为 2k + 1

此时,由于除法只会返回商,所以一个节点无论它是左子节点还是右子节点,其父节点都是 k / 2

需要注意的是,为了与参数上的索引对应,我们不使用 a[0]

3.3 原理

主要的原理是如何去重新排序一个二叉堆
当我们进行比较和交换的时候,二叉堆的顺序将会被打破,所以我们需要重建二叉堆(reheapifying)

主要的算法思想是上浮下沉
当一个节点获得了更高的优先级的时候,我们将其上浮,通常是由于我们在二叉堆的底部插入了一个新节点导致的。

当一个节点优先级降低时,我们将它下沉,通常是我们用一个低优先级的节点替换了根节点的时候(其实是进行了删除操作)

  1. 上浮

    当一个节点比他的父节点大的时,我们将它和它的父亲交换以恢复二叉堆的次序
    这是一个递归的操作,如果上浮后还存在二叉堆次序损坏,那么就继续上浮

  2. 下沉

    当一个节点比它的两个子节点都要小的时候,我们将它与较大的子节点交换以恢复二叉堆的次序 如果下沉之后仍存在此情况,继续下沉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private void swim(int k) {
while(k > 1 && less(k / 2, k)) {
exch(k, k / 2);
k = k / 2;
}
}

private void sink(int k) {
while(k * 2 < N) {
int j = k * 2;

if (less(j, j + 1)) {
j ++:
}

if (!less(k, j)) {
break;
}

exch(k, j);
k = j;
}
}

3.4 实现

  1. 插入元素

    我们将一个新元素插入到数组尾部,增大堆的大小,然后将元素上浮

  2. 删除最大元素

    我们将位于数组尾部的元素根节点交换,然后删除原来的根节点,将新的根节点下沉

1
2
3
4
5
6
7
8
9
10
11
12
public void insert(Key v) {
pq[++ N] = v;
swim(N);
}

public Key delMax() {
Key max = pq[1];
exch(1, N--);
pq[N + 1] = null; // Prevent the object free
sink(1);
return max;
}

4. 索引优先队列

索引优先队列是一种带了索引的优先队列;

这里的索引指的是,队列中的元素 在队列的位置。

至于优先队列为何需要索引,实际上是为了方便修改队列里的数据。

有了这个索引,我们就可以处理一些大型的输入数据(甚至可能都没办法一次性读入内存的数据),或者在一些小内存机器上工作

主要的改变有:

  1. 我们将元素和它的索引一起插入

  2. 我们删除最大元素的时候,返回它的索引

4.1 实现

使用 3 个数组:

  1. pq[]

    优先队列的堆,下标是堆的位置,值是 索引

  2. qp[]

    索引数组,是 pq[] 的反转,值是堆的位置

  3. keys[]

    对象数组,下标是索引,值是对象本身

4.2 使用优先队列的多项归并

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
public class Multiway {

public static void merge(In[] streams) {
int N = streams.lenth;
// Notice tha the N is the number of the STREAM,
// not the input strings.
IndexMinPQ<String> pq = new IndexMinPQ<String> (N);

for (int i = 0; i < N; i++) {
if (!streams[i].isEmpty()) { // That is a Stream
// Insert the stream
pq.insert(i, streams[i].readString());
}
}

while (!pq.isEmpty()) {
// Output the Min element
StdOut.println(pq.min());
int i = pq.delMin();

// Keep reading next String
if (!streams[i].isEmpty()) {
pq.insert(i, streams[i].readString());
}
}

}


public static void main(String[] args) {
int N = args.lenth;
In[] streams = new In[N];
for (int i = 0; i < N; i++) {
streams[i] = new In(args[i]);
}
merge(streams);
}
}

5. 堆排序

堆排序是优先队列的一种应用;
它将元素插入到优先队列中,然后通过删除最大元素或者删除最小元素来达到排序的目的

这个算法由于使用了优先队列,它能处理一些特别大型的数据,或者在一些小内存机器上使用。

它包含了两个步骤,建立二叉堆销毁二叉堆

5.1 实现原理

5.1.1 建立二叉堆

需要注意的是,数组其实就是一个二叉堆!
所以我们只需要对数组进行二叉堆重建(reheapifying),那么建立的步骤就完成了

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

5.1.2 销毁二叉堆(排序)

二叉堆可以帮助我们获取最大或者最小的元素,所以我们只需要将其删除出二叉堆,然后插入到一个新数组就可以了。

但是要注意的是,我们应该如何去删除最大的元素呢?
实际上,我们不需要真正的“删除”这个元素(即释放它的内存);
我们只是在进行排序,所以我们只需要将它交换,或者说将它放到正确的位置,即可。

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

5.2 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void sort(Comparable[] a) {
int N = a.lenth;

/**
* Build the heap
* We only need to traversal the nodes
* who contains children.
* As the heap's theory, we convince that the k = N/2
*/
for (int k = N/2; k >= 1; k--) {
sink(a, k, N);
}

// Destory the heap
while (N>1) {
exch(a,1, N--);
sink(a, 1, N);
}
}

注意,如果需要升序,应该使用删除最大元素的二叉堆;

同理,如果需要降序,应该使用删除最小元素的二叉堆;

因为交换使得删除的元素被交换到了数组尾部。

需要注意的是,我们这里使用的是 1-base 的堆,而普通的数组是 0-base 的;

所以需要在索引计算上小心谨慎。

5.3 性能

进行 NN 个数据元素的排序,堆排序仅仅需要 (2NlgN+2N)(2NlgN + 2N) 次的比较和一半的交换

虽然它的时间复杂度是线性级别的,但是它需要很少的内存就可以处理很大型的数据。

同时,堆排序在最坏情况下可以保证 NlogNNlogN 的复杂度,而且是原地排序(不需要多余空间)

尽管如此,堆排序的应用仍然没有快速排序广泛和频繁,主要是因为:

  1. 堆排序的内循环比快速排序要复杂

    循环技术和各种需要注意的地方较快速排序多

  2. 堆排序不能有效利用缓存

    堆排序载入大数组时,数组的引用会很可能布满整个内存,而快速排序是递归调用,保留着很多局部的引用,所以快速排序在利用缓存的效率上比堆排序高。

    现代机器的缓存命中率一般都会在 95% 以上,所以有效的利用缓存是很重要的

  3. 同时和归并排序相比,堆排序是不稳定的,在开发一些要求排序稳定性的程序时,显然应该选择归并排序