优先队列
队列是一种先进先出的结构，队列末尾插入，队列开头出队。但是优先队列是什么呢？优先队列打破了队列的特性，有两种优先队列：
- 最大优先队列：无论入队顺序如何，出队时都是最大元素出队
- 最小优先队列：无论入队顺序如何，出队时都是最小元素出队
最大优先队列可以使用最大堆进行实现，每一次入队操作都是堆的插入操作，每一次出队都是删除堆顶节点。
public class PriorityQueue {
private int[] array;
private int size;
public PriorityQueue(int size) {
array = new int[size];
}
public void enqueue(int value) {
if (size >= array.length) {
resize();
}
array[size++] = value;
upAdjust(array);
}
public int dequeue() throws Exception {
if (size < 0) {
throw new Exception("queue is empty!");
}
int head = array[0];
array[0] = array[--size];
downAdjust();
return head;
}
private void upAdjust(int[] array) {
int childIndex = size - 1;
int parentIndex = (childIndex - 1) / 2;
int temp = array[childIndex];
while (childIndex > 0 && array[parentIndex] < array[childIndex]) {
array[childIndex] = array[parentIndex];
childIndex = parentIndex;
parentIndex = (childIndex - 1) / 2;
}
array[childIndex] = temp;
}
private void downAdjust() {
int parenIndex = 0;
int childIndex = 2 * parenIndex + 1;
int temp = array[parenIndex];
while (parenIndex < size) {
if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]) {
childIndex ++;
}
if (temp >= array[childIndex]) {
break;
}
array[parenIndex] = array[childIndex];
parenIndex = childIndex;
childIndex = 2 * parenIndex + 1;
}
array[parenIndex] = temp;
}
private void resize() {
int newSize = this.size * 2;
this.array = Arrays.copyOf(this.array, newSize);
}
@Override
public String toString() {
return Arrays.toString(array);
}
public static void main(String[] args) throws Exception {
PriorityQueue priorityQueue = new PriorityQueue(32);
priorityQueue.enqueue(3);
priorityQueue.enqueue(5);
priorityQueue.enqueue(10);
priorityQueue.enqueue(2);
priorityQueue.enqueue(7);
System.out.println(priorityQueue.toString());
System.out.println("出队：" + priorityQueue.dequeue());
System.out.println("出队：" + priorityQueue.dequeue());
}
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-05-06，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读