个性化阅读
专注于IT技术分析

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

如何实现优先队列?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());
}
赞(0) 打赏
未经允许不得转载:srcmini » 如何实现优先队列?Java使用数组实现最小堆和优先队列
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

觉得文章有用就打赏一下文章作者

微信扫一扫打赏