二叉堆的特性（基于二叉树结构）

1. 最大堆的堆顶是整个堆中的最大元素
2. 最小堆的堆顶是整个堆中的最小元素

二叉堆的的插入和删除（包含堆的重建）时间复杂度都是O（logn），构建是O（n）

下面是图解（借用了图片）
1.插入过程
第一步：

image.png

第二步：

image.png

第三步：

image.png

2.删除过程
第一步：

image.png

第二步：

image.png

第三步：

image.png

第四步：

image.png

第五步：

image.png

第六步：

image.png

以下为代码实现

public class BinaryHeap {

    // 上浮
    public static void upAdjust(int[] array) {
        // 找出最后一个节点
        int childIndex = array.length - 1;
        // 先拿出需要上浮节点的值
        int temp = array[childIndex];
        // 根据推算找出节点的父节点
        int parentIndex = (childIndex - 1) / 2;

        while (childIndex > 0 && array[parentIndex] > temp) {
            // 如果父节点值大于子节点，则进行交换
            array[childIndex] = array[parentIndex];

            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        array[parentIndex] = temp;
    }

    public static void downAdjust(int[] array, int parentIndex, int length) {
        // 先拿出父节点的值
        int parentData = array[parentIndex];
        // 得到左子节点的位置
        int childIndex = 2 * parentIndex + 1;

        // 当子节点的下标已经超出数组下标，跳出循环
        while (childIndex < length) {

            // 定位左子节点和右子节点的大小
            if (childIndex + 1 < array.length && array[childIndex + 1] < array[childIndex]) {
                childIndex++;
            }
            // 如果父节点小于任何一个子节点则跳出
            if (parentData < array[childIndex]) {
                return;
            }

            // 将子节点上浮，然后下标进行下浮
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }

        // 最后跳出循环的点，是父节点已经不存在子节点了，已经遍历到根节点，进行赋值
        array[parentIndex] = parentData;
    }

    public static void main(String[] args) {
        int[] array = new int[] {1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
        upAdjust(array);
        System.out.println(Arrays.toString(array));

        array = new int[] {7, 1, 3, 10, 5, 2, 8, 9, 6};
        buildHeap(array);
        System.out.println(Arrays.toString(array));
    }

    private static void buildHeap(int[] array) {
        // 构造二叉堆
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            downAdjust(array, i, array.length);
        }
    }

public class PriorityQueue {

    int[] array = new int[10];
    int size;

    public void enQueue(int data) {
        if (size == array.length) {
            resize();
        }
        // 放到最后一个位置
        array[size++] = data;
        upAdjust();
    }

    private void upAdjust() {
        int childIndex = size - 1;
        int childData = array[childIndex];
        int parentIndex = (childIndex - 1) / 2;

        while (childIndex > 0 && array[parentIndex] < childData) {
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        array[childIndex] = childData;
    }

    private int deQueue() {

        if (size == 0) {
            throw new IndexOutOfBoundsException("队列为空");
        }

        int waitPopData = array[0];
        array[0] = array[--size];

        downAdjust();

        return waitPopData;
    }

    private void downAdjust() {
        int parentIndex = 0;
        int childIndex = 1;
        int temp = array[parentIndex];

        while (childIndex < size) {
            if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]) {
                childIndex++;
            }
            if (temp >= array[childIndex]) {
                break;
            }

            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        array[parentIndex] = temp;
    }

    private void resize() {
        array = Arrays.copyOf(array, array.length*2);
    }

    public static void main(String[] args) {
        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.enQueue(3);
        priorityQueue.enQueue(5);
        priorityQueue.enQueue(5);
        priorityQueue.enQueue(10);
        priorityQueue.enQueue(2);
        priorityQueue.enQueue(2);
        priorityQueue.enQueue(7);
        priorityQueue.enQueue(7);
        priorityQueue.enQueue(1);
        priorityQueue.enQueue(1);
        priorityQueue.enQueue(8);
        priorityQueue.enQueue(4);
        priorityQueue.enQueue(4);
        System.out.println("出队元素" + priorityQueue.deQueue());
        System.out.println("出队元素" + priorityQueue.deQueue());
        System.out.println("出队元素" + priorityQueue.deQueue());
        System.out.println("出队元素" + priorityQueue.deQueue());
        System.out.println("出队元素" + priorityQueue.deQueue());
        System.out.println("出队元素" + priorityQueue.deQueue());
        System.out.println("出队元素" + priorityQueue.deQueue());
        System.out.println("出队元素" + priorityQueue.deQueue());
        System.out.println("出队元素" + priorityQueue.deQueue());
    }
}