以下代码基于最小堆实现的最小优先队列

二叉堆实现参见 --> 二叉堆、堆排序

自定义实现优先队列

/**
 * @ClassName 最小优先队列
 * @Description 基于最小堆堆实现的优先队列
 * @Author Deng PeiLin
 * @Date 2022/1/13 15:47
 **/
public class 优先队列 {

    private int[] arr;
    private int size;

    public 优先队列 () {
        this.arr = new int[1];
    }

    /**
     * 入队
     */
    public 优先队列 add(int data){
        if (size >= arr.length) {
            resize();
        }
        arr[size ++] = data;
        upAdjust();
        return this;
    }

    /**
     * 出队
     */
    public int out(){
        if (size <= 0){
            throw new RuntimeException("队列中无数据");
        }
        int firstData = arr[0];
        arr[0] = arr[--size];
        downAdjust();

        return firstData;
    }

    /**
     * 上浮调整
     */
    private void upAdjust() {
        int childIndex = size - 1;
        int parentIndex = (childIndex - 1) / 2;
        // temp 用于保存插入的叶子节点值, 用于最后的赋值
        int temp = arr[childIndex];
        while (childIndex > 0 && temp < arr[parentIndex]) {
            // 无需真正交换, 单项赋值即可
            arr[childIndex] = arr[parentIndex];
            childIndex = parentIndex;
            parentIndex = (parentIndex - 1) / 2;
        }
        arr[childIndex] = temp;
    }

    /**
     * 下沉调整
     */
    private void downAdjust() {
        int parentIndex = 0;
        // temp 用于保存插入的叶子节点值, 用于最后的赋值
        int temp = arr[parentIndex];
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < size) {
            // 如果有右节点, 且右节点小于左节点的值, 则定位到右节点
            if (childIndex + 1 < size && arr[childIndex + 1] < arr[childIndex]) {
                childIndex++;
            }
            // 如果父节点小于子节点的值则跳出, 不需要调整
            if (temp < arr[childIndex]) {
                break;
            }
            arr[parentIndex] = arr[childIndex];
            parentIndex = childIndex;
            childIndex = childIndex * 2 + 1;
        }
        arr[parentIndex] = temp;
    }

    private void resize() {
        arr = Arrays.copyOf(arr, size * 2);
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        return Arrays.toString(Arrays.copyOfRange(arr, 0, size));
    }
}

测试代码

public static void main(String[] args){

        优先队列 queue = new 优先队列();

        queue.add(5).add(8).add(9).add(11).add(999).add(1);
        System.out.println("队列数据: " + queue);

        int out = queue.out();
        System.out.println("出队元素: " + out);
        System.out.println("队列数据: " + queue);

        int out2 = queue.out();
        System.out.println("出队元素: " + out2);
        System.out.println("队列数据: " + queue);

    }

测试结果 >>> 以最小堆实现的最小优先队列, 队列头部皆为最小数据

队列数据: [1, 8, 5, 11, 999, 9]
出队元素: 1
队列数据: [5, 8, 9, 11, 999]
出队元素: 5
队列数据: [8, 11, 9, 999]

Process finished with exit code 0