优先队列：和之前的队列类似，但是这里的优先队列加入了优先级，优先队列是允许至少下列两种操作的数据结构：insert（插入），它的作用是显而易见的；以及deleteMin（删除最小者），它的工作是找出、返回并删除优先队列中最小的元素。优先队列我们一般使用二叉堆来实现。下面首先看二叉堆的实现。
二叉堆
堆是一颗被完全填满的二叉树，有可能的例外是最底层，底层上的元素从左到右填入，即只有最下面两层节点的度（子树的个数）能小于2。这是堆的结构性。这里二叉树其实是使用数组来保存数据，其中父节点总是小于子节点，这是堆的堆序性。对于数组中任意位置i上的元素，其左儿子在位置2i上，右儿子在左儿子后的单元（2i+1）中，它的父亲则在位置（i/2）上，其中数组的第0个位置无数据。下面是相关实现：
package cn.list;
public class MyBinaryHeap<T extends Comparable<? super T>> {
private static final int DEFAULT_CAPACITY = 10;
private int currentSize;
private T[] array;
public MyBinaryHeap() {
this(DEFAULT_CAPACITY);
}
public MyBinaryHeap(int capacity) {
currentSize = 0;
array = (T[])new Comparable[ capacity + 1 ];
}
public MyBinaryHeap(T[] items) {
currentSize = items.length;
array = (T[]) new Comparable[(currentSize + 2) * 11 / 10];//????
int i = 1;
for (T item : items) {
array[i++] = item;
}
buildHeap();
}
public void insert(T x) {
if (currentSize == array.length - 1) {
enlargeArray(array.length * 2 + 1);//扩容
}
int hole = ++currentSize;
//先在数组最后创建一个空穴，如果x小于空穴的父亲，则空穴上虑
for (; hole > 1 && x.compareTo(array[hole / 2]) < 0; hole /= 2) {
array[hole] = array[hole / 2];
}
array[hole] = x;
}
//根处节点总是小于子节点
public T findMin() {
if (isEmpty()) {
return null;
}
return array[1];
}
//删除根节点后留下一个空穴，我们将此空穴下虑。下虑到最后时使用数组原来最后一个元素填充
public T deleteMin() {
if (isEmpty()) {
System.out.println("空树");
throw new RuntimeException();
}
T minItem = findMin();
array[1] = array[currentSize--];
percolateDown(1);
return minItem;
}
public boolean isEmpty() {
return currentSize == 0;
}
public void makeEmpty() {
currentSize = 0;
}
private void percolateDown(int hole) {
int child;
T tmp = array[hole];
for (; hole * 2 <= currentSize; hole = child) {
child = hole * 2;
if (child != currentSize && array[child + 1].compareTo(array[child]) < 0) {
child++;
}
if (array[child].compareTo(tmp) < 0) {
array[hole] = array[child];
} else {
break;
}
}
array[hole] = tmp;
}
//在构建堆的时候，每碰到一个元素都需要下虑
private void buildHeap() {
for (int i = currentSize / 2; i > 0; i--) {
percolateDown(i);
}
}
//扩容
private void enlargeArray(int newSize) {
if(newSize < currentSize){
return ;
}
T[] old = array;
array = (T[])new Object[newSize];
for(int i = 0; i < size(); i++){
array[i] = old[i];
}
}
public int size(){
return currentSize;
}
public boolean isFull() {
return currentSize == array.length - 1;
}
}
说明：上面的代码是数据结构与算法（java）书中的，下面看一个稍简单的实现。
（转自：http://blog.csdn.net/tuke_tuke/article/details/50358606）
Heap.java
package cn.list;
import java.util.ArrayList;
//来自网上，二叉堆的实现
public class Heap<E extends Comparable> {
private ArrayList<E> list = new ArrayList<E>();// 用数组实现堆
public Heap() {
}
public Heap(E[] objects) {
for (int i = 0; i < objects.length; i++) {
add(objects[i]);
}
}
public void add(E newObject) {// 添加一个元素
list.add(newObject);
int currentIndex = list.size() - 1;
while (currentIndex > 0) {
int parentIndex = (currentIndex - 1) / 2;// 找到该结点的父结点
if (list.get(currentIndex).compareTo(list.get(parentIndex)) > 0) {// 与父节点比较
// 如果当前结点的值大于父结点就交换位置
E temp = list.get(currentIndex);
list.set(currentIndex, list.get(parentIndex));
list.set(parentIndex, temp);
} else
break;
currentIndex = parentIndex;
}
}
public E remove() {// 删除并返回根结点,堆的特点是移除了根结点后还是堆
if (list.size() == 0)
return null;
E removeObject = list.get(0);
list.set(0, list.get(list.size() - 1));// 把最后一个结点放在根结点的位置
list.remove(list.size() - 1);
int currentIndex = 0;
while (currentIndex < list.size()) {
int leftChildIndex = 2 * currentIndex + 1;
int rightChildIndex = 2 * currentIndex + 2;// 左右孩子结点的坐标
if (leftChildIndex >= list.size())
break;
// 比较左右孩子的值，使maxIndex指向值大的结点
int maxIndex = leftChildIndex;
if (rightChildIndex < list.size()) {
if (list.get(maxIndex).compareTo(list.get(rightChildIndex)) < 0) {
maxIndex = rightChildIndex;
}
}
// 如果当前结点的值小于其左右孩子中的大的值，就交换两个结点
if (list.get(currentIndex).compareTo(list.get(maxIndex)) < 0) {
E temp = list.get(maxIndex);
list.set(maxIndex, list.get(currentIndex));
list.set(currentIndex, temp);
currentIndex = maxIndex;
} else
break;
}
return removeObject;
}
public int getSize() {
return list.size();
}
}
优先队列
MyPriorityQueue.java
package cn.list;
//优先队列实现
public class MyPriorityQueue<E extends Comparable> {
private Heap<E> heap = new Heap<E>();// 用堆实现优先队列
// 入队列
public void enqueue(E e) {
heap.add(e); // 这个add以后，堆会自己调整成一个新堆
}
// 出队列
public E dequeue() {
return heap.remove();// 这移除出之后，堆会自己调整，还是一个新堆
}
public int getSize() {
return heap.getSize();
}
}
测试
package cn.list;
public class TestMyPriorityQueue {
public static void main(String[] args) {
Patient p1 = new Patient("John", 2);
Patient p2 = new Patient("Tom", 9);
Patient p3 = new Patient("Jack", 4);
Patient p4 = new Patient("Michael", 6);
MyPriorityQueue<Patient> priorityQueue = new MyPriorityQueue<>();
priorityQueue.enqueue(p1);
priorityQueue.enqueue(p2);
priorityQueue.enqueue(p3);
priorityQueue.enqueue(p4);
while (priorityQueue.getSize() > 0) {
System.out.print(priorityQueue.dequeue() + " ");
}
}
static class Patient implements Comparable {
private String name;
private int priority;
public Patient(String name, int priority) {
this.name = name;
this.priority = priority;
}
public String toString() {
return name + "(priority:" + priority + ")";
}
public int compareTo(Object obj) {// 比较优先级
return ((Patient) obj).priority - this.priority;
}
}
}
