Fork me on GitHub
秋染蒹葭

数据结构与算法之五：优先队列

发表于 | 分类于 |

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （largest-in，first-out）的行为特征。

基本概念

抽象数据类型，优先队列的接口同前面讲到的队列的接口一样，是其基于泛型的API接口代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public interface Queue<E> {
    //队列是否为空
    boolean isEmpty();
    //队列的大小
    int size();
    //入队
    void enQueue(E element);
    //出队
    E deQueue();
}

基于数组实现的优先队列

实现优先队列最简的方法就是基于前面讲到的基于数组的栈的代码，只需对插入或删除操作作相应的更改即可。

基于有序数组的实现

在栈的代码的插入方法中添加代码，将所有较大的元素向右移动一格，以保证数组有序（和插入排序相同），这里我们可以使用二分查找的方法来找出元素应插入的位置，然后再移动元素。这样最大元素，总是在数组的最右边，其删除操作和栈的实现中一样。

代码：

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/**
 * 基于有序数组的实现的优先队列
 * @author Alent
 * @param <E>
 */
public class PriorityQueue<E extends Comparable<E>> implements Queue<E>{
    private E[] elements;
    private int size=0;
    
    @SuppressWarnings("unchecked")
    public PriorityQueue() {
        elements = (E[])new Comparable[1]; 
    }
    
    @Override public int size() {return size;}
    @Override public boolean isEmpty() {return size == 0;}
    @Override
    public void enQueue(E element) {
        if(size == elements.length) {
            resizingArray(2*size);//若数组已满将长度加倍
        }
        elements[size++] = element;
        insertSort(elements);
    }
    @Override
    public E deQueue() {
        E element = elements[--size];
        elements[size] = null;     //注意：避免对象游离
        if(size > 0 && size == elements.length/4) {
            resizingArray(elements.length/2);//小于数组1/4,将数组减半
        }
        return element;
    }
    
    //插入排序，由于前面n-1个元素是有序的，这里只插入最后一个元素
    public void insertSort(E[] a) {
        int N = size -1; //最后一个元素是size-1，不是a.length-1
        if(N == 0) return;
        int num = binaryFind(a, a[N], 0, N-1);
        E temp = a[N];
        //num后的元素向后移动
        for (int j = N; j > num; j--) {
           a[j] = a[j-1];
        }
        a[num] = temp;
    }
    //找出元素应在数组中插入的位置
    public int binaryFind(E[] a, E temp, int down, int up) {
        if(up<down || up>a.length || down<0) {
            System.out.println("下标错误");
        }
        if(temp.compareTo(a[down]) < 0) return down;
        if(temp.compareTo(a[up]) > 0) return up+1;
        int mid = (up-down)/2 + down;
        if(temp.compareTo(a[mid]) == 0) {
            return mid + 1;
        }else if(temp.compareTo(a[mid])<0) {
            up = mid-1;
        }else if(temp.compareTo(a[mid])>0) {
            down = mid+1;
        }
        return binaryFind(a,temp,down,up);
    }
    //交换两个元素
    public void swap(E[] a,int i,int j) {
        E temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    //调整数组大小
    public void resizingArray(int num) {
        @SuppressWarnings("unchecked")
        E[] temp = (E[])new Comparable[num];
        for(int i=0;i<size;i++) {
            temp[i] = elements[i];
        }
        elements = temp;
    }
    
    public static void main(String[] args) {
        int[] a = {4,2,1,3,8,new Integer(5),7,6};//测试数组
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        System.out.print("入栈顺序：");
        for(int i=0;i<a.length;i++) {
            System.out.print(a[i]+" ");
            pq.enQueue(a[i]);
        }
        System.out.println();
        System.out.print("出栈顺序数组实现：");
        while(!pq.isEmpty()) {
            System.out.println(pq.deQueue());
        }
    }
}

基于无序数组的实现

同样，我们一个可以在删除方法中修改，在删除方法中添加一段类似于选择排序内循环的代码，每次删除时先找出数组中的最大元素，然后与最右边元素进行交换，然后在删除元素。

代码：

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
@Override
public void enQueue(E element) {
    if(size == elements.length) {
        resizingArray(2*size);//若数组已满将长度加倍
    }
    elements[size++] = element;
}
@Override
public E deQueue() {
    swapMax(elements);
    E element = elements[--size];
    elements[size] = null;     //注意：避免对象游离
    if(size > 0 && size == elements.length/4) {
        resizingArray(elements.length/2);//小于数组1/4,将数组减半
    }
    return element;
}
public void swapMax(E[] a) {
    int max = size -1;
    for(int i=0;i<size-1; i++) {
        if(larger(a[i],a[max])) 
            max = i;
    }
    swap(a, size-1, max);
}
//比较两个元素大小
public boolean larger(E a1, E a2) {
    return a1.compareTo(a2)>0;
}

基于堆实现的优先队列

基本概念：

  • 当一个二叉树的每个结点都大于等于它的两个子结点时，我们称它是堆有序的。根结点是堆有序的二叉树的最大结点。
  • 二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级存储。

一棵堆有序的完全二叉树:

为了操作方便，这是我们使用一个数组，来表示一个堆。我们不使用数组的第一个元素，具体实现在《树》中有提及，这里就不说了。

堆的有序化

当我们将元素插入到堆（数组的末尾）中时，插入的元素可能比它的父结点要大，堆的有序状态被打破。我们需要交换它和它的父节点来修堆，直到堆重新变为有序状态。其操作如下图：

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//上浮操作
private void swim(int k) {
        while(k > 1 && less(k/2, k)) {
            swap(k/2, k);
            k = k/2;
        }
    }
private boolean less(int i, int j) {
    return elements[i].compareTo(elements[j]) < 0;
}
//交换两个元素
public void swap(int i,int j) {
    E temp = elements[i];
    elements[i] = elements[j];
    elements[j] = temp;
}

同样的，当我们从堆中删除根结点并将它的最后一个元素放到顶端时，堆的有序性被打破，我们需要将它与它的两个子结点种的较大者进行交换，以恢复堆的有序性，其操作流程如下图：

其代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
//下沉操作
private void sink(int k) {
    while(2*k <= size) {
        int j = 2*k;
        if(j < size && less(j, j+1))
            j++;
        if(!less(k,j))
            break;
        swap(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
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
57
58
59
60
61
62
63
64
/**
 * 基于堆的优先队列
 * @author Alent
 */
public class MaxPQ<E extends Comparable<E>> implements Queue<E>{
    private E[] elements;
    private int size=0;
    
    @SuppressWarnings("unchecked")
    public MaxPQ(int capacity) {
        elements = (E[])new Comparable[capacity + 1]; 
    }
    
    @Override public int size() {return size;}
    @Override public boolean isEmpty() {return size == 0;}
    @Override
    public void enQueue(E element) {
        elements[++size] = element;
        swim(size);
    }
    
    //上浮
    private void swim(int k) {
        while(k > 1 && less(k/2, k)) {
            swap(k/2, k);
            k = k/2;
        }
    }
    
    private boolean less(int i, int j) {
        return elements[i].compareTo(elements[j]) < 0;
    }
    @Override
    public E deQueue() {
        E result = elements[1];
        swap(1, size--);
        elements[size + 1] = null;
        sink(1);
        return result;
    }
    
    //下沉
    private void sink(int k) {
        while(2*k <= size) {
            int j = 2*k;
            if(j < size && less(j, j+1))
                j++;
            if(!less(k,j))
                break;
            swap(k,j);
            k = j;
        }
    }
    //交换两个元素
    public void swap(int i,int j) {
        E temp = elements[i];
        elements[i] = elements[j];
        elements[j] = temp;
    }
}

三种实现方法的时间复杂度比较：

索引优先队列

索引优先队列，它用一个索引数组保存了某个元素在优先队列中的位置，使得我们能够引用已经进入优先队列中的元素。最在些应用中，通常是很有必要的，如：有向图的Dijkstra算法中就使用了索引优先队列，来返回最小边的索引。

其实现方法为：

使用elements[]数组来保存队列中的元素，pq[]数组用来保存elements中元素的索引，在添加一个数组qp[]来保存pq[]的逆序——qp[i]的值是i在pq[]中的位置（即 pq[qp[i]] = i）。若i不在队列中，则令qp[i] = -1。辅助函数less()、swap()、sink()、swim()和前面优先队列中的一样。

索引优先队列的代码实现：

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/**
 * 基于堆实现的索引优先队列
 */
public class IndexMinPQ<E extends Comparable<E>>{
    private int[] pq; //索引二叉堆
    private int[] qp; // 保存逆序：pq[qp[i]] = i;
    private E[] elements; //元素
    private int size = 0;
    @SuppressWarnings("unchecked")
    public IndexMinPQ(int capacity) {
        elements = (E[]) new Comparable[capacity + 1];
        pq = new int[capacity + 1];
        qp = new int[capacity + 1];
        for (int i = 0; i <= capacity; i++) {
            qp[i] = -1;
        }
    }
    public boolean isEmpty() {
        return size == 0;
    }
    //删除最小元素，并返回索引
    public int delMin() {
        int index = pq[1];
        swap(1, size--);
        sink(1);
        elements[pq[size + 1]] = null;
        qp[pq[size + 1]] = -1;
        return index;
    }
    //删除索引k及其元素
    public void delete(int k) {
        int index = qp[k];
        swap(index, size--);
        swim(index);
        sink(index);
        elements[k] = null;
        qp[k] = -1;
    }
    
    //插入元素，将它和索引k关联
    public void insert(int k, E element) {
        size++;
        qp[k] = size;
        pq[size] = k;
        elements[k] = element;
        swim(size);
    }
     //改变索引k关联的元素
    public void change(int k, E element) {
        elements[k] = element;
        swim(qp[k]);
        sink(qp[k]);
    }
    
    //是否包含索引k
    public boolean contains(int k) {
        return qp[k] != -1;
    }
    
    //下沉
    private void sink(int k) {
        while (2 * k <= size) {
            int j = 2 * k;
            if (j < size && less(j, j + 1))
                j++;
            if (!less(k, j))
                break;
            swap(k, j);
            k = j;
        }
    }
    //上浮
    private void swim(int k) {
        while (k > 1 && less(k / 2, k)) {
            swap(k, k / 2);
            k = k / 2;
        }
    }
    private boolean less(int i, int j) {
        return elements[pq[i]].compareTo(elements[pq[j]]) > 0;
    }
    //交换两元素
    private void swap(int i, int j) {
        int swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }
}

索引优先队列的时间复杂度：

总结

这里在堆排序中有很好的应用。

参考资料

本文标题:数据结构与算法之五：优先队列

文章作者:zhyjor

发布时间:2018年03月31日 - 12:03

最后更新:2023年10月11日 - 02:10

原始链接:https://zhyjor.github.io/2018/03/31/数据结构与算法之五：优先队列/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

🐶 您的支持将鼓励我继续创作 🐶

热评文章