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

  • 最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队；
  • 最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队；

可以使用最大堆和最小堆来分别实现最大优先队列和最小优先队列。

代码实现

  1. public class PriorityQueue {
  3.     private int[] array;
  4.     private int size;
  6.     public PriorityQueue() {
  7.         // 队列初始长度为 32
  8.         array = new int[32];
  9.     }
  11.     // 扩容
  12.     public void resize() {
  13.         // 队列容量翻倍
  14.         int newSize = this.size * 2;
  15.         this.array = Arrays.copyOf(this.array, newSize);
  16.     }
  18.     // 上浮
  19.     private void upAdjust() {
  20.         int childIndex = size - 1;
  21.         int parentIndex = (childIndex - 1) / 2;
  22.         // temp 保存插入的叶子节点值，用于最后的赋值
  23.         int temp = array[childIndex];
  24.         while (childIndex > 0 && temp > array[parentIndex]) {
  25.             // 无需真正交换，单项赋值即可
  26.             array[childIndex] = array[parentIndex];
  27.             childIndex = parentIndex;
  28.             parentIndex = parentIndex / 2;
  29.         }
  30.         array[childIndex] = temp;
  31.     }
  33.     // 下沉
  34.     private void downAdjust() {
  35.         // temp 保存父节点的值，用于最后赋值
  36.         int parentIndex = 0;
  37.         int childIndex = 1;
  38.         int temp = array[parentIndex];
  39.         while (childIndex < size) {
  40.             // 如果有右孩子，且右孩子值大于左孩子，则定位到右孩子
  41.             if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]) {
  42.                 childIndex++;
  43.             }
  44.             // 如果父节点大于任何一个孩子的值，直接跳出
  45.             if (temp >= array[childIndex]) break;
  46.             // 无需真正交换，单向赋值即可
  47.             array[parentIndex] = array[childIndex];
  48.             parentIndex = childIndex;
  49.             childIndex = 2 * childIndex + 1;
  50.         }
  51.         array[parentIndex] = temp;
  52.     }
  54.     // 入队
  55.     public void enQueue(int key) {
  56.         // 队列长度超出范围，扩容
  57.         if (size >= array.length) {
  58.             resize();
  59.         }
  60.         array[size++] = key;
  61.         upAdjust();
  62.     }
  64.     // 出队
  65.     public int deQueue() throws Exception {
  66.         if (size <= 0) {
  67.             throw new Exception("the queue if empty!");
  68.         }
  69.         // 获取堆顶元素
  70.         int head = array[0];
  71.         // 让最后一个元素移动到堆顶
  72.         array[0] = array[--size];
  73.         downAdjust();
  74.         return head;
  75.     }
  77.     public static void main(String[] args) throws Exception {
  78.         PriorityQueue priorityQueue = new PriorityQueue();
  79.         priorityQueue.enQueue(3);
  80.         priorityQueue.enQueue(5);
  81.         priorityQueue.enQueue(10);
  82.         priorityQueue.enQueue(2);
  83.         priorityQueue.enQueue(7);
  84.         System.out.println("出队元素：" + priorityQueue.deQueue());
  85.         System.out.println("出队元素：" + priorityQueue.deQueue());
  86.     }
  87. }

上述代码采用数组来存储二叉堆的元素，因此当元素数量超过数组长度时，需要进行扩容来扩大数组长度。