优先队列priority queue是允许至少下列两种操作的数据结构：insert插入以及deleteMin（删除最小者），它的工作是找出，返回并删除优先队列中最小的元素。insert操作等价于enqueue入队，而deleteMin则是dequeue出队在优先队列中的等价操作。
一种实现优先队列的方法是使用二叉堆binary heap，它的使用对于优先队列的实现相当普遍，以至于当堆heap这个词不加修饰地用在优先队列的上下文中时，一般都是指数据结构的这种实现。在本节，我们把二叉堆只叫做堆。像二叉查找树一样，堆也有两个性质，即结构性和堆序性。恰似AVL树，对堆的一次操作可能破坏这两个性质中的一个，因此，堆得操作必须到堆得所有性质都被满足时才能终止。事实上这并不难做到。
堆是一棵被完全填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树。容易证明，一棵高为h的完全二叉树有2^h到2^(h+1)-1个节点。这意味着完全二叉树的高是logN向下取整，显然它是O(logN)。
一个重要的观察发现，因为完全二叉树这么有规律，所以它可以用一个数组表示而不需要使用链。对于数组中任一位置i上的元素，其左儿子在位置2i上，右儿子在左儿子后的单元(2i+1)中，它的父亲则在位置i/2中。因此，这里不仅不需要链，而且遍历该树所需要的操作极简单，在大部分计算机上运行很可能非常快。这种实现的唯一问题在于，最大的堆大小需要事先估计，但一般这并不成问题。
以下是一个二叉堆的实现：
import java.util.NoSuchElementException;
import java.util.Random;
public class BinaryHeap<AnyType extends Comparable<? super AnyType>> {
private static final int DEFAULT_CAPACITY = 10;// 默认容量
private int currentSize; // 当前堆大小
private AnyType[] array; // 数组
public BinaryHeap() {
this(DEFAULT_CAPACITY);
}
@SuppressWarnings("unchecked")
public BinaryHeap(int capacity) {
currentSize = 0;
array = (AnyType[]) new Comparable[capacity + 1];
}
@SuppressWarnings("unchecked")
public BinaryHeap(AnyType[] items) {
currentSize = items.length;
array = (AnyType[]) new Comparable[(currentSize + 2) * 11 / 10];
int i = 1;
for (AnyType item : items) {
array[i++] = item;
}
buildHeap();
}
/**
* 从任意排列的项目中建立堆，线性时间运行
*/
private void buildHeap() {
for (int i = currentSize / 2; i > 0; i--) {
percolateDown(i);
}
}
/**
* 堆内元素向下移动
*
* @param hole
* 下移的开始下标
*/
private void percolateDown(int hole) {
int child;
AnyType 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;
}
/**
* 插入一个元素
*
* @param x
* 插入元素
*/
public void insert(AnyType x) {
if (isFull()) {
enlargeArray(array.length * 2 + 1);
}
int hole = ++currentSize;
for (; hole > 1 && x.compareTo(array[hole / 2]) < 0; hole /= 2) {
array[hole] = array[hole / 2];
}
array[hole] = x;
}
/**
* 堆是否满
*
* @return 是否堆满
*/
public boolean isFull() {
return currentSize == array.length - 1;
}
/**
* 堆是否空
*
* @return 是否堆空
*/
public boolean isEmpty() {
return currentSize == 0;
}
/**
* 清空堆
*/
@SuppressWarnings("unused")
public void makeEmpay() {
currentSize = 0;
for (AnyType anyType : array) {
anyType=null;
}
}
/**
* 找到堆中最小元素
* @return 最小元素
*/
public AnyType findMin() {
if (isEmpty())
return null;
return array[1];
}
/**
* 删除堆中最小元素
* @return 删除元素
*/
public AnyType deleteMin() {
if (isEmpty()) {
throw new NoSuchElementException();
}
AnyType minItem = findMin();
array[1] = array[currentSize];
array[currentSize--] = null;
percolateDown(1);
return minItem;
}
/**
* 扩大数组容量
* @param newSize 新的容量
*/
@SuppressWarnings("unchecked")
private void enlargeArray(int newSize) {
AnyType[] old = array;
array = (AnyType[]) new Comparable[newSize];
for (int i = 0; i < old.length; i++) {
array[i] = old[i];
}
}
/**
* 输出数组中的元素
*/
public void printHeap() {
for (AnyType anyType : array) {
System.out.print(anyType + " ");
}
}
public static void main(String[] args) {
BinaryHeap<Integer> heap = new BinaryHeap<Integer>();
for (int i = 0; i < 20; i++) {
heap.insert(i);
}
heap.deleteMin();
heap.deleteMin();
heap.deleteMin();
heap.printHeap();
}
}
执行结果：
null 3 4 5 7 9 11 6 15 8 17 10 18 12 13 14 19 16 null null null null null