什么是优先队列？
在之前，我们先回顾一下普通队列的特点。
- 普通队列的特点是先进先出，后进后出。
那优先队列的特点是什么呢？优先队列的出队顺序和入队顺序无关，有优先级相关。在这里分为两种情况：
- 最大优先队列，无论入队顺序如何，都是最大的元素优先出队。
- 最小优先队列，无论入队顺序如何，都是最小的元素优先出队。
例如有一个最大优先队列，其中的最大元素是10，那么虽然10并不是队头元素，但出队时仍然让元素10首先出队。
优先队列的实现
先来回顾一下堆的特点。
- 最大堆的堆顶是整个堆中最大的元素。
- 最小堆的堆顶是整个堆中最小的元素。
因此，可以通过最大堆来实现最大优先队列，这样的话，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶操作。
1、入队操作
假设，有如下这样的堆。如图：
上图中插入新节点52，这时会与父节点进行比较，如果大于父节点，那么上浮到合适的位置，否则不用任何的操作。
2、出队操作
-
让堆顶节点62出队
-
把最后一个节点16替换到堆顶位置。
-
这时，堆顶与它的左右孩子中最大的节点进行比较，如果小于，进行下沉操作到合适的位置，否则不用任何操作。
3、代码实现
/**
* 描述：基于数组二次封装成动态数组。
* <p>
* Create By ZhangBiao
* 2020/5/15
*/
public class Array<E> {
private E[] data;
private int size;
/**
* 构造函数，传入数组的容量capacity构造Array。
*
* @param capacity 容量大小
*/
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}
/**
* 无参数的构造函数，默认数组的容量capacity=10。
*/
public Array() {
this(10);
}
public Array(E[] arr) {
this.data = (E[]) new Object[arr.length];
for (int i = 0; i < arr.length; i++) {
this.data[i] = arr[i];
}
this.size = this.data.length;
}
/**
* 获取数组的容量。
*
* @return
*/
public int getCapacity() {
return data.length;
}
/**
* 获取数组中的元素个数。
*
* @return
*/
public int getSize() {
return size;
}
/**
* 返回数组是否为空。
*
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 向所有元素后添加一个新元素
*
* @param e
*/
public void addLast(E e) {
/*if (size == data.length) {
throw new IllegalArgumentException("AddLast failed. Array is full.");
}
data[size] = e;
size++;*/
add(size, e);
}
public void addFirst(E e) {
add(0, e);
}
/**
* 在index索引的位置插入一个新元素e
*
* @param index
* @param e
*/
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
}
if (size == data.length) {
resize(2 * data.length);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
/**
* 扩容
*
* @param newCapacity
*/
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
/**
* 获取index索引位置的元素。
*
* @param index
* @return
*/
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get failed. Index is illgal.");
}
return data[index];
}
/**
* 获取索引为0的元素。
*
* @return
*/
public E getFirst() {
return get(0);
}
/**
* 获取索引为size-1的元素。
*
* @return
*/
public E getLast() {
return get(size - 1);
}
/**
* 修改index索引位置的元素为e。
*
* @param index
* @param e
*/
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Set failed. Index is illegal.");
}
data[index] = e;
}
/**
* 查找数组中是否有元素e。
*
* @param e
* @return
*/
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i] == e) {
return true;
}
}
return false;
}
/**
* 查找数组中元素e所在的索引，如果不存在元素e，则返回-1。
*
* @param e
* @return
*/
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i] == e) {
return i;
}
}
return -1;
}
/**
* 从数组中删除index位置的元素，返回删除的元素。
*
* @param index
* @return
*/
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Remove failed. Index is illegal.");
}
E ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return ret;
}
/**
* 从数组中删除第一个元素并返回删除的元素。
*
* @return
*/
public E removeFirst() {
return remove(0);
}
/**
* 从数组中删除最后一个元素并返回删除的元素。
*
* @return
*/
public E removeLast() {
return remove(size - 1);
}
/**
* 从数组中删除元素e。
*
* @param e
*/
public void removeElement(E e) {
int index = find(e);
if (index != -1) {
remove(index);
}
}
public void swap(int i, int j) {
if (i < 0 || i >= size || j < 0 || j >= size) {
throw new IllegalArgumentException("Index is Illegal");
}
E temp = data[i];
data[i] = data[j];
data[j] = temp;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size = %d , capacity = %d
", size, data.length));
res.append('[');
for (int i = 0; i < size; i++) {
res.append(data[i]);
if (i != size - 1) {
res.append(", ");
}
}
res.append(']');
return res.toString();
}
}
/**
* 描述：基于动态数组实现二叉堆（最大堆）。
* <p>
* Create By ZhangBiao
* 2020/5/15
*/
public class MaxHeap<E extends Comparable<E>> {
private Array<E> data;
public MaxHeap(int capacity) {
this.data = new Array<>(capacity);
}
public MaxHeap() {
this.data = new Array<>();
}
public MaxHeap(E[] arr) {
this.data = new Array<>(arr);
for (int i = parent(arr.length - 1); i >= 0; i--) {
siftDown(i);
}
}
/**
* 返回堆的元素个数
*
* @return
*/
public int size() {
return data.getSize();
}
/**
* 返回一个布尔值，表示堆是否为空
*
* @return
*/
public boolean isEmpty() {
return data.isEmpty();
}
/**
* 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
*
* @param index
* @return
*/
private int parent(int index) {
if (index == 0) {
throw new IllegalArgumentException("index-0 doesn't have parent");
}
return (index - 1) / 2;
}
/**
* 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
*
* @param index
* @return
*/
private int leftChild(int index) {
return index * 2 + 1;
}
/**
* 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
*
* @param index
* @return
*/
private int rightChild(int index) {
return index * 2 + 2;
}
/**
* 向堆中添加元素
*
* @param e
*/
public void add(E e) {
data.addLast(e);
siftUp(data.getSize() - 1);
}
private void siftUp(int k) {
while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
data.swap(k, parent(k));
k = parent(k);
}
}
/**
* 查看堆中的最大元素
*
* @return
*/
public E findMax() {
if (data.getSize() == 0) {
throw new IllegalArgumentException("Can not findMax when heap is empty");
}
return data.get(0);
}
/**
* 取出堆中最大元素
*
* @return
*/
public E extractMax() {
E ret = findMax();
data.swap(0, data.getSize() - 1);
data.removeLast();
siftDown(0);
return ret;
}
private void siftDown(int k) {
while (leftChild(k) < data.getSize()) {
int j = leftChild(k);
if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
j++;
}
if (data.get(k).compareTo(data.get(j)) >= 0) {
break;
}
data.swap(k, j);
k = j;
}
}
public static void main(String[] args) {
int n = 1000000;
MaxHeap<Integer> maxHeap = new MaxHeap<>();
Random random = new Random();
for (int i = 0; i < n; i++) {
maxHeap.add(random.nextInt(Integer.MAX_VALUE));
}
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = maxHeap.extractMax();
}
for (int i = 1; i < n; i++) {
if (arr[i - 1] < arr[i]) {
throw new IllegalArgumentException("Error");
}
}
System.out.println("Test MaxHeap completed.");
}
/**
* 取出堆中的最大元素并替换成元素e
*
* @param e
* @return
*/
public E replace(E e) {
E ret = findMax();
data.set(0, e);
siftDown(0);
return ret;
}
}
/**
* 描述：队列所需的方法。
*
* Create By ZhangBiao
* 2020/5/15
*/
public interface Queue<E> {
/**
* 入队操作
*
* @param e
*/
void enqueue(E e);
/**
* 出队操作
*
* @return
*/
E dequeue();
/**
* 获取队首
*
* @return
*/
E getFront();
/**
* 获取队列元素个数
*
* @return
*/
int getSize();
/**
* 判断队列是否为空
*
* @return
*/
boolean isEmpty();
}
/**
* 描述：基于二叉堆（最大堆）实现优先队列。
* <p>
* Create By ZhangBiao
* 2020/5/15
*/
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
private MaxHeap<E> heap;
public PriorityQueue() {
this.heap = new MaxHeap();
}
@Override
public void enqueue(E e) {
heap.add(e);
}
@Override
public E dequeue() {
return heap.extractMax();
}
@Override
public E getFront() {
return heap.findMax();
}
@Override
public int getSize() {
return heap.size();
}
@Override
public boolean isEmpty() {
return heap.isEmpty();
}
}