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

发表于 更新于 阅读次数：

前言

堆之最大优先队列的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
package com;

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

    private T[] data;
    private int maxPriorityQueueLength;

    MaxPriorityQueue(int capacity) {
        this.data = (T[]) new Comparable[capacity+1];
    }

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

    // 判断队列是否为空
    public boolean isEmpty() {
        return maxPriorityQueueLength==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[++maxPriorityQueueLength] = t;
        swim(maxPriorityQueueLength);
    }

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

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

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

            if (!less(k, max)) {
                break;
            }

            exch(k, max);

            k = max;
        }
    }

}

完成

哔哩哔哩——黑马程序员