如何实现优先队列？Java使用数组实现最小堆和优先队列

一、什么是优先队列？和普通队列有什么区别？

优先队列就是一个元素带有权值（priority）的队列，这个权值又叫做优先级，入队和普通队列一样入队，出队按照权值的大小进行优先出队。权值最小的元素先出队的叫做最小优先队列，权值最大的元素先出队的叫做最大优先队列。

二、优先队列和堆有什么关系？优先队列就是堆吗？

优先队列和堆是不一样的数据结构，但是它们的概念相似，堆主要就是用来实现优先队列的，相近的分类有最小堆和最大堆。一般是使用最小堆实现最小优先队列，使用最大堆实现最大优先队列，无论哪一种堆，实现方式都是相似的，另外堆的种类有很多种，如二叉堆、左式堆、斐波那契堆、二项堆等，因此本文说的最小堆和优先队列差不多是一个意思，实现最小堆也就是实现最小优先队列，准确的来说，我们是使用最小堆来实现优先队列。如下图是一个最小二叉堆：

三、优先队列有什么作用？

优先队列的作用非常多，它的主要特征是按照优先级的大小进行优先出队。优先队列结合其它算法可以实现取得最优值，而且时间界也比较好，标准操作的一般时间为O(n)。例如贪婪算法中可以使用优先队列，Dijkstra算法也属于贪婪算法，其中可以使用优先队列按照距离的大小对顶点进行储存。相似的，A*算法和D*算法也可以使用优先队列，可以大大降低寻路时间。另外，在回溯算法和分支限界法都也可以使用优先队列，一般来说，联机算法中的排序操作或取优操作都可以使用优先队列。

四、Java如何用数组实现优先队列？

如上图，是一个逻辑形式的二叉堆以及相应的数组，数组索引和二叉堆中的元素一一对应，你可以发现第i个结点的父结点索引为(i-1)/2，左儿子索引为2*i+1，右儿子索引为2*i+2，根据这个规律，我们可以使用数组表示一个二叉堆，也就是最小堆或最小优先队列，下面我们使用Java来实现一个优先队列。

首先我们希望，这个优先队列可以储存任何类型的数据，所以这里使用泛型T，并且因为是优先队列，所以需要到T获取权值，我们让它实现一个接口：

public interface TypeInterface {

    // 获取权值或优先级
    long getKey();

    // 设置权值或优先级
    void setKey(long key);
}

之后在优先队列的操作中，需要使用权值的时候可以使用getKey获取，更改权值使用SetKey。优先队列的设计中，你可以直接使用一个T数组，但是注意要设计一个capacity数组容量，这里不使用T数组，而是使用一个ArrayList，和数组是一样的，只是没有上界限制，完全实现代码如下：

// Java实现优先队列，最小堆
public class PriorityQueue<T extends TypeInterface>{

    private int size;
    private ArrayList<T> array;

    // 优先队列构造函数
    public PriorityQueue() {
        this.size = 0;
        this.array = new ArrayList<>();
    }

    // 使用一个数组构建一个优先队列
    public PriorityQueue(ArrayList<? extends T> list){
        this.size = list.size();
        this.array = new ArrayList<>(list);
    }

    // 检查优先队列是否已空
    public boolean isEmpty(){
        return this.size == 0;
    }

    // 获取父结点位置
    private int parent(int i){
        return (i - 1) / 2;
    }

    // 获取左儿子位置
    private int left(int i){
        return 2 * i + 1;
    }

    // 获取右儿子位置
    private int right(int i){
        return 2 * i + 2;
    }

    private void swap(int i, int j){
        T temp = array.get(i);
        array.set(i, array.get(j));
        array.set(j, temp);
    }

    // 往队列中添加元素
    public void push(T value){
        if(value == null)
            throw new NullPointerException();
        this.size++;
        int i = this.size - 1;
        array.add(i, value);
        // 上滤
        while(i != 0 && array.get(i).getKey() < array.get(parent(i)).getKey()){
            swap(i, parent(i));
            i = parent(i);
        }
    }

    // 下滤
    private void heapify(int i){
        int left = left(i);
        int right = right(i);
        int small = i;
        if(left < this.size && array.get(left).getKey() < array.get(i).getKey())
            small = left;
        if(right < this.size && array.get(right).getKey() < array.get(small).getKey())
            small = right;
        if(small != i){
            swap(i, small);
            heapify(small);
        }
    }

    // 从堆顶取出一个元素
    public T pop(){
        if(this.isEmpty())
            return null;
        if(this.size == 1){
            T v = array.get(0);
            this.size--;
            return v;
        }
        T value = array.get(0);
        array.set(0, array.get(this.size - 1));
        this.size--;
        heapify(0);
        return value;
    }

    // 根据数据索引降低关键字的值到value
    public void decreaseKey(int i, long value){
        if(this.isEmpty() || i >= this.size)
            return;
        array.get(i).setKey(value);
        // 上滤
        while(i != 0 && array.get(i).getKey() < array.get(parent(i)).getKey()){
            swap(i, parent(i));
            i = parent(i);
        }
    }

    // 根据索引删除一个数据
    public void delete(int i){
        if(this.isEmpty() || i >= this.size)
            return;
        this.decreaseKey(i, Integer.MIN_VALUE);
        this.pop();
    }

    // 快速构建一个堆
    public void buildHeap(){
        if(this.isEmpty())
            return;
        for(int i = this.size / 2;i >= 0;i--)
            heapify(i);
    }

}

五、Java优先队列的使用

首先如果我们要将一个数据添加到优先队列中，需要保证这个类实现了上面的TypeInterface接口，这里给出的例子为Lengua类，如下：

public class Lengua implements TypeInterface{

    private long id;
    private String name;

    public Lengua(long id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public long getKey() {
        return this.id;
    }

    @Override
    public void setKey(long key) {
        this.id = key;
    }

    public long getId() {
        return id;
    }

    public void setId(long id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

最后，下面是就是这个优先队列的使用和调用实例，第一个例子是属于联机算法的例子，也就是在算法执行过程中，获取一个数据添加一个，第二个例子属于脱机算法，也就是已知所有的数据的情况下，构建一个优先队列，下面是完整调用源码：

// 例子1
PriorityQueue<Lengua> heap = new PriorityQueue<>();
Lengua espanol = new Lengua(90, "espanol");
Lengua chino = new Lengua(50, "chino");
Lengua italiano = new Lengua(48, "italiano");
Lengua frances = new Lengua(31, "frances");
Lengua aleman = new Lengua(29, "aleman");
heap.push(espanol);
heap.push(chino);
heap.push(italiano);
heap.push(frances);
heap.push(aleman);
heap.decreaseKey(3, 16);
while (!heap.isEmpty()){
    Lengua lengua = heap.pop();
    System.out.println(lengua.getId() + "   " + lengua.getName());
}

System.out.println();

// 例子2
ArrayList<Lengua> list = new ArrayList<>();
list.add(espanol);
list.add(chino);
list.add(italiano);
list.add(frances);
list.add(aleman);
PriorityQueue<Lengua> h = new PriorityQueue<>(list);
h.buildHeap();
while (!h.isEmpty()){
    Lengua lengua = h.pop();
    System.out.println(lengua.getId() + "   " + lengua.getName());
}