优先队列

优先队列 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 */
}
}

特性