什么是优先队列？【转】

这一次，我们来讲一讲二叉堆的另外一个应用：优先队列

队列的特点是什么？

聪明的小伙伴们都知道，是先进先出（fifo）。

入队列：

出队列：

那么，优先队列又是什么样子呢？

优先队列不再遵循先入先出的原则，而是分为两种情况：

• 最大优先队列，无论入队顺序，当前最大的元素优先出队。

• 最小优先队列，无论入队顺序，当前最小的元素优先出队。

比如有一个最大优先队列，它的最大元素是8，那么虽然元素8并不是队首元素，但出队的时候仍然让元素8首先出队：

要满足以上需求，利用线性数据结构并非不能实现，但是时间复杂度较高，最坏时间复杂度o（n），并不是最理想的方式。

至于为什么最坏时间复杂度是o（n），大家可以思考下。

让我们回顾一下二叉堆的特性：

1. 最大堆的堆顶是整个堆中的最大元素
2. 最小堆的堆顶是整个堆中的最小元素

因此，我们可以用最大堆来实现最大优先队列，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。

入队操作：

1. 插入新节点5

1. 新节点5上浮到合适位置。

出队操作：

1. 把原堆顶节点10“出队”

1. 最后一个节点1替换到堆顶位置

1. 节点1下沉，节点9成为新堆顶

public class priorityqueue {

private int[] array;
private int size;
public priorityqueue(){
//队列初始长度32
array = new int[32];
}
/**
* 入队
* @param key 入队元素
*/
private void enqueue(int key) {
//队列长度超出范围，扩容
if(size >= array.length){
resize();
}
array[size++] = key;
upadjust();
}
/**
* 出队
*/
private int dequeue() throws exception {
if(size <= 0){
throw new exception("the queue is empty !");
}
//获取堆顶元素
int head = array[0];
//最后一个元素移动到堆顶
array[0] = array[--size];
downadjust();
return head;
}
/**
* 上浮调整
*/
private void upadjust() {
int childindex = size-1;
int parentindex = childindex/2;
// temp保存插入的叶子节点值，用于最后的赋值
int temp = array[childindex];
while (childindex > 0 && temp > array[parentindex])
{
//无需真正交换，单向赋值即可
array[childindex] = array[parentindex];
childindex = parentindex;
parentindex = parentindex / 2;
}
array[childindex] = temp;
}
/**
* 下沉调整
*/
private void downadjust() {
// temp保存父节点值，用于最后的赋值
int parentindex = 0;
int temp = array[parentindex];
int childindex = 1;
while (childindex < size) {
// 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
if (childindex + 1 < size && array[childindex + 1] > array[childindex]) {
childindex++;
}
// 如果父节点大于任何一个孩子的值，直接跳出
if (temp >= array[childindex])
break;
//无需真正交换，单向赋值即可
array[parentindex] = array[childindex];
parentindex = childindex;
childindex = 2 * childindex + 1;
}
array[parentindex] = temp;
}
/**
* 下沉调整
*/
private void resize() {
//队列容量翻倍
int newsize = this.size * 2;
this.array = arrays.copyof(this.array, newsize);
}
public static void main(string[] args) throws exception {
priorityqueue priorityqueue = new priorityqueue();
priorityqueue.enqueue(3);
priorityqueue.enqueue(5);
priorityqueue.enqueue(10);
priorityqueue.enqueue(2);
priorityqueue.enqueue(7);
system.out.println("出队元素：" + priorityqueue.dequeue());
system.out.println("出队元素：" + priorityqueue.dequeue());
}
}

代码中采用数组来存储二叉堆的元素，因此当元素超过数组范围的时候，需要进行resize来扩大数组长度。