原理

基于数组完成二叉堆的构建，根据父结点n，俩个子节点为2n、2n+1这个基本规律可以构建一个完全二叉树，且所有父结点都满足大于子结点这个规则。通过上浮和下沉操作恢复堆的有序性，满足在logN时间复杂度下完成插入和删除操作。

API

package leetcode.May;

/**
 * @description: 基于二叉堆的优先队列
 * @author: qiangyuecheng
 * @date: 2022/5/26 21:04
 */
public class PriorityQueue {

    private int[] source;
    private int index;

    public void init() {
        source = new int[10];
        index = 0;
    }

    /**
     * 插入
     */
    public void insert(int i) {
        //放到最后，上浮
        source[++index] = i;
        up();
    }

    /**
     * 删除头
     */
    public int delete() {
        //删除头，最后元素放到头，下沉
        int res = source[1];
        source[1] = source[index--];
        down();
        return res;
    }

    /**
     * 上浮
     */
    public void up() {
        int x = index;
        while (x > 1 && source[x] > source[x / 2]) {
            swap(x, x / 2);
            x /= 2;
        }
    }

    /**
     * 下沉
     */
    public void down() {
        int x = 1;
        while (2 * x <= index) {
            int maxIndex = source[x * 2] > source[x * 2 + 1] ? x * 2 : x * 2 + 1;
            if (source[x] < source[maxIndex]) {
                swap(x, maxIndex);
                x = maxIndex;
            } else {
                break;
            }
        }
    }

    public void swap(int i, int j) {
        int tmp = source[i];
        source[i] = source[j];
        source[j] = tmp;
    }


    public static void main(String[] args) {
        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.init();
        priorityQueue.insert(3);
        priorityQueue.insert(4);
        priorityQueue.insert(1);
        priorityQueue.insert(3);
        priorityQueue.insert(4);

        System.out.printf("" + priorityQueue.delete());
        System.out.printf("" + priorityQueue.delete());
        System.out.printf("" + priorityQueue.delete());


    }
}