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

c64556ae12a7accedcbac4cc291ed2a2.png

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

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

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

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

911510980537e9b98e92e574d080a996.png

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

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

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

772e96013ad0fa9961b09265dccf1e5d.png

如上图,是一个逻辑形式的二叉堆以及相应的数组,数组索引和二叉堆中的元素一一对应,你可以发现第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{

private int size;

private ArrayList 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 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 list = new ArrayList<>();

list.add(espanol);

list.add(chino);

list.add(italiano);

list.add(frances);

list.add(aleman);

PriorityQueue h = new PriorityQueue<>(list);

h.buildHeap();

while (!h.isEmpty()){

Lengua lengua = h.pop();

System.out.println(lengua.getId() + " " + lengua.getName());

}