【代码】堆之最小优先队列

发表于 更新于 阅读次数：

前言

堆之最小优先队列Java版API实现

源代码

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
package com;

public class MinPriorityQueue<T extends Comparable<T>> {

    private T[] data;

    private int minPriorityQueueLength;

    MinPriorityQueue() {

    }

    // 获取队列元素的个数
    public int size() {
        return minPriorityQueueLength;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return minPriorityQueueLength==0;
    }

    // 判断堆中索引i处的元素是否小于索引j处的元素
    private boolean less(int i, int j){
        return data[i].compareTo(data[j])<0;
    }

    // 交换堆中i索引处和j索引处的值
    private void exch(int i, int j) {
        T tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

    // 往队列中插入一个元素
    public void insert(T t) {
        data[++minPriorityQueueLength] = t;
        swim(minPriorityQueueLength);
    }

    // 删除堆中最小的元素并返回这个最大的元素
    public T delMim() {
        T min = data[1];
        exch(1, minPriorityQueueLength);
        minPriorityQueueLength--;
        sink(1);
        return min;
    }

    // 使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
    private void swim(int k) {
        while (k>1) {
            if (less(k, k/2)) {
                exch(k, k/2);
            }

            k = k/2;
        }
    }

    // 使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
    private void sink(int k) {
        while (2*k<=minPriorityQueueLength) {
            int min;
            if (2*k+1<=minPriorityQueueLength) {
                if (less(2*k, 2*k+1)) {
                    min = 2*k;
                } else {
                    min = 2*k+1;
                }
            } else {
                min = 2*k;
            }

            if (less(k, min)) {
                break;
            }

            exch(k, min);

            k = min;
        }
    }

}

完成

参考文献

哔哩哔哩——黑马程序员