堆排序的应用-优先队列

堆排序在排序复杂性的研究中有着重要的地位,因为它是我们所知的唯一能够同时最优的利用空间和时间的方法-在最坏的情况下它能保证使用~2NlgN次比较和恒定的额外空间。

在开始了解优先队列之前我们先了解一下堆的特性:

一个大根堆有这么个特性,它的爸爸总是比它的俩孩子的值大;除了这个最基本的以外,你还要知道第k个元素的左孩子是2k,右孩子是2k+1;知道这个以后,下面我们需要实现两个方法,高效的删除最大元素和插入元素

如果新插入一个数,那么根据前面的特性,只需要不断循环的用自身和自己的爸爸(k/2)比较大小,根据比较结果判断是否要交换位置即可;如果要删掉一个最大的数,只需要将根与最后一个数交换位置(因为根是大根堆中最大的数),将其脱离堆结构,然后将根节点不断和它的孩子(2K、2K+1)比较大小,下沉到合适位置即可;

为了满足k,2k,2k+1的这种层级关系,后续将舍弃数组下标为0的位置,因为2*0会影响到这种层级关系的判断。

下面我们说一下下沉(sink)和上浮(swim)的实现方法

上浮

如果堆的有序状态因为某个节点比它的父节点更大而被打破,那么我们就需要通过交换它和它的父节点来修复堆。

1
2
3
4
5
6
7
8
private void swim(int k){

while(k > 1 && less(k/2,k)){
exch(k/2,k);
k = k/2;
}

}

下沉

与上浮相反,如果堆有序被打破,k节点想要下沉到合适的位置,代码应该这么写。

1
2
3
4
5
6
7
8
9
10
private void sink(int 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;
}
}

基于堆的优先队列

下面我们实现一下堆的优先队列。优先队列由一个基于堆的完全二叉树表示,存储于数组pq[1…N]中,pq[0]不用,代码如下:

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
54
55
56

public class MaxPQ<Key extends Comparable<Key>>{

private Key[] pq;
private int N = 0;

public MaxPQ(int maxN){
pq = (Key[]) new Comparable[maxN + 1];
}

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

public int size (){

return N;

}

public void insert(Key v){

pq[++N] = v;
swim(N);

}

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

private boolean less(int i,int j){
return pq[i] < pq[j];
}

private void exch(i,j){

Key t = pq[i];
pq[i] = pq[j];
pq[j] = t;

}

private void swim(int k){
...
}

private void sink(int k){
...
}

}

在insert()中,将N加1并把新元素添加到数组最后,然后用swim()恢复秩序。在delMax()中。从pq[1]中得到需要返回的元素,然后将pq[N]移动到pq[1],将N减一并用sink()恢复对的秩序。将pq[N+1]设为null,以便GC回收其所占空间。