优先队列与堆排序

发表于   |   分类于

优先队列 API

Requirement. Generic items are Comparable.

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>>
    // create an empty priority queue
    MaxPQ()
    
    // create a priority queue with given keys
    MaxPQ(Key[] a)
    
    // insert a key into the priority queue
    void insert(Key v)
    
    // return and remove the largest key
    Key delMax()
    
    // is the priority queue empty?
    boolean isEmpty()
    
    // return the largest key
    Key max()
    
    // number of entries in the priority queue
    int size()

优先队列：无序数组实现

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
public class UnorderedMaxPQ<Key extends Comparable<Key>>
{
    // pq[i] = ith element on pq
    private Key[] pq;
    // number of elements on pq
    private int N;

    public UnorderedMaxPQ(int capacity) {
        // no generic array creation
        pq = (Key[]) new Comparable[capacity];
    }
    
    public boolean isEmpty() {
        return N == 0;
    }
    
    public void insert(Key x) {
        pq[N++] = x;
    }

    public Key delMax() {
        int max = 0;
        for (int i = 1; i < N; i++)
            if (less(max, i)) max = i;
        exch(max, N-1);
        // null out entry to prevent loitering
        return pq[--N];
 }

完全二叉树

Binary tree: Empty or node with links to left and right binary trees.
Complete tree: Perfectly balanced, except for bottom level

性质：Height of complete tree with N nodes is lg N.

二叉树数组表示

  • Indices start at 1.
  • Take nodes in level order.
  • No explicit links needed!

二叉树性质

  • Largest key is a[1], which is root of binary tree.
  • Can use array indices to move through tree
    • Parent of node at k is at k/2.
    • Children of node at k are at 2k and 2k+1.

Promotion in a heap

场景：Child’s key becomes larger key than its parent’s key

解决方案：

  • Exchange key in child with key in parent.
  • Repeat until heap order restored.
1
2
3
4
5
6
7
private void swim (int k) {
    while (k > 1 && less(k/2, k)) {
        // parent of node at k is at k/2
        exch(k, k/2);
        k = k/2;
    }
}

Insertion in a heap

插入：Add node at end, then swim it up.
Cost：At most 1 + lg N compares.

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

Demotion in a heap

场景：Parent’s key becomes smaller than one (or both) of its children’s.

解决方案：

  • Exchange key in parent with key in larger child.
  • Repeat until heap order restored.
1
2
3
4
5
6
7
8
9
10
private void sink (int k) {
    while (2*k <= N) {
        int j = 2*k;
        // children of node at k are 2k and 2k+1
        if (j < N && less(j, j+1)) j++;
        if (!less(k, j)) break;
        exch(k, j);
        k = j;
    }
}

Delete the maximum in a heap

删除最大元素：Exchange root with node at end, then sink it down.
Cost：At most 2 lg N compares.

1
2
3
4
5
6
7
8
public Key delMax() {
    Key max = pq[1];
    exch(1, N--);
    sink(1);
    // prevent loitering
    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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;
    private int N;
    
    public MaxPQ(int capacity) {
        pq = (Key[]) new Comparable[capacity+1];
    }

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

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

    public Key delMax() {
        Key max = pq[1];
        exch(1, N--);
        sink(1);
        // prevent loitering
        pq[N+1] = null;
        return max;
    }

    private void swim(int k) {
        while (k > 1 && less(k/2, k)) {
            // parent of node at k is at k/2
            exch(k, k/2);
            k = k/2;
        }
    }
    
    private void sink(int k) {
        while (2*k <= N) {
            int j = 2*k;
            // children of node at k are 2k and 2k+1
            if (j < N && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }

    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }
    
    private void exch(int i, int j) {
        Key t = pq[i]; pq[i] = pq[j]; pq[j] = t;
    }
}

堆排序

基本步骤

构建堆

排序

Java 实现

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
public class Heap {
    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int k = N/2; k >= 1; k--)
            sink(a, k, N);
        
        while (N > 1) {
            exch(a, 1, N);
            sink(a, 1, --N);
        }
    }

    private static void sink(Comparable[] a, int k, int N) {
        /* as before */
    }

    private static boolean less(Comparable[] a, int i, int j) {
        /* as before */
        /* but convert from
        1-based indexing to
        0-base indexing */
    }

    private static void exch(Comparable[] a, int i, int j) {
        /* as before */
        /* but convert from
        1-based indexing to
        0-base indexing */
    }
}

特性

总结

完全二叉堆特性

  • 二叉堆中最大的节点位于 a[1]
  • N 个节点的完全二叉堆的高度为 lg[N]
  • 节点 k 的父节点为 k/2
  • 几点 k 的子节点为 2k 和 2k+1

主要实现

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>>
{
    // 两个私有变量：表示堆的结构的数组 pq，以及表示堆的大小的 N
    private Key[] pq;
    private int N;
    
    // 构造一个堆
    public MaxPQ(int capacity)
    
    // 堆所包含的函数方法
    public boolean isEmpty() // 判断二叉堆是否为空
    public void insert(Key key) // 插入一个新的堆节点
    public Key delMax() // 删除这个堆中的最大节点
    
    // 实现堆所需的辅助函数
    private void swim(int k) // 使一个较大的节点上升到合适的节点
    private void sink(int k) // 使一个较小的节点下沉到合适的节点
    
    // 数组的辅助函数
    private boolean less(int i, int j) // 比较数组里 i 和 j 的节点大小
    private void exch(int i, int j) // 交换位置 i 和 j 的节点位置