如何实现优先队列（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); }

【如何实现优先队列（Java使用数组实现最小堆和优先队列）】之后在优先队列的操作中，需要使用权值的时候可以使用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 =http://www.srcmini.com/= 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()); }