优先队列和堆排序

Wafer Li ... 2017-02-12 《Algorithm 第四版》笔记
  • Algorithm
  • 读书笔记
大约 7 分钟

# 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. 下沉

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

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 3.4 实现

  1. 插入元素

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

  2. 删除最大元素

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

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;
}
1
2
3
4
5
6
7
8
9
10
11
12

# 4. 索引优先队列

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

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

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

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

主要的改变有:

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

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

# 4.1 实现

使用 3 个数组:

  1. pq[]

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

  2. qp[]

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

  3. keys[]

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

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

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);
    }
}
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

# 5. 堆排序

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

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

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

# 5.1 实现原理

# 5.1.1 建立二叉堆

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

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

# 5.1.2 销毁二叉堆(排序)

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

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

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

# 5.2 实现

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

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

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

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

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

# 5.3 性能

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

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

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

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

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

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

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

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

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

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