优先队列

优先队列

我们知道普通队列的特点是先进先出，但是优先队列的特点则遵守以下两条规则：
- 最大优先队列：无论入队的顺序，当前最大的元素先出列。
- 最小优先队列：无论入队的顺序，当前最小的元素先出列。

说明：在学习优先队列前必须先理解二叉堆

这时候就是二叉堆发挥作用的时候了。我们知道二叉堆有以下特性：
- 最大堆：堆顶是整个数组中最大的元素，且任何父节点的值都大于其子节点
- 最小堆：堆顶是整个数组中最小的元素，且任何父节点的值都小于其子节点

操作

对于优先队列，介绍以下几种操作：
入队操作；
出队操作；
说明：以最小优先队列为例

1.入队操作
优先队列本质上就是用二叉堆来实现的，每次插入一个数据都是插入到数据数组的最后一个位置，然后再做上浮操作，如果插入的数是数组中最大数，自然会上浮到堆顶。如“图1 入队操作”所示：

图1 入队操作

2.出队操作
出队操作就是返回堆顶最小堆的数据之后用数组最后的数插入到堆顶，之后再做下沉操作。如“图2 出队操作”所示：

图2 出队操作

时间复杂度

因为二叉堆上浮和下沉的时间复杂度都为log2(n)，所以入队和出队的时间复杂度也是log2(n)。

代码

package Queue;

import java.util.Arrays;

public class PriorityQueue {

    private int[] array;
    private int size; // 当前队列长度

    public PriorityQueue() {
        this.array = new int[8];
    }

    /**
     * 出入数据
     * @param value 要插入的数据
     */
    public void enQueue(int value){
        // 先判断队列长度是否超出范围，是则扩容
        if (size >= array.length) {
            reSize();
        }
        array[size++] = value;
        upAdjust();
    }

    /**
     * 取出堆顶数据，并删除（置零）数组最后一个数据
     * @return 堆顶数据
     */
    public int deQueue() {
        int res = array[0];
        array[0] = array[--size];
        array[size] = 0;
        downAdjust();
        return res;
    }

    /**
     * 扩容
     */
    private void reSize() {
        int newSize = this.size * 2;
        this.array = Arrays.copyOf(this.array, newSize);
    }

    /**
     * 上浮操作
     */
    private void upAdjust() {
        int childrenIndex = size - 1;
        int parentIndex =  (childrenIndex - 1) / 2;
        // 先保存刚插入的叶子节点的值，用于最后赋值
        int temp = array[childrenIndex];
        // 开始上浮操作
        while (childrenIndex > 0 && temp < array[parentIndex]) {
            // 直接单向赋值，无需转换
            array[childrenIndex] = array[parentIndex];
            childrenIndex = parentIndex;
            parentIndex = (childrenIndex - 1) / 2;
        }
        // 最后赋值
        array[childrenIndex] = temp;
    }

    /**
     * 下沉操作
     */
    private void downAdjust() {
        int parentIndex = 0;
        int temp = array[parentIndex];
        int length = size - 1;
        // 假设有左子节点，先求出左子节点的下标
        int childrenIndex = 2 * parentIndex + 1;
        // 当确实是有左子节点时
        while (childrenIndex <= length) {
            // 如果有右子节点且左子节点大于右子节点时，则将 childrenIndex 设置为右子节点的下标值
            if ((childrenIndex + 1) <= length && array[childrenIndex + 1] < array[childrenIndex]) {
                childrenIndex++;
            }
            // 如果无需下沉，则直接跳出循环
            if (temp <= array[childrenIndex]) {
                break;
            }
            // 接下来才是真正的下沉
            array[parentIndex] = array[childrenIndex];
            parentIndex = childrenIndex;
            childrenIndex = 2 * parentIndex + 1;
        }
        // 最后的赋值
        array[parentIndex] = temp;
    }

    @Override
    public String toString() {
        System.out.println(Arrays.toString(this.array));
        return null;
    }

    public static void main(String[] args) {
        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.enQueue(5);
        priorityQueue.enQueue(3);
        priorityQueue.enQueue(6);
        priorityQueue.enQueue(9);
        priorityQueue.enQueue(8);
        priorityQueue.enQueue(6);
        priorityQueue.enQueue(7);
        priorityQueue.enQueue(2);
        priorityQueue.enQueue(4);
        priorityQueue.enQueue(6);
        priorityQueue.enQueue(3);
        priorityQueue.toString();
        System.out.println("堆顶数据：" + priorityQueue.deQueue());
        priorityQueue.toString();
    }
}

总结

优先队列是基于二叉堆实现的，优先指的是按某种优先级优先出列而不是先入先出。操作系统的阻塞机制正是有优先队列实现。