数据结构与算法(四)：二叉堆和优先队列

本篇是上篇 数据结构与算法(三)：树 和 二叉树(http://www.gxitsky.com/article/1602671933412749) 的延续。

二叉堆 是一种特殊的堆，本质上是一种完全二叉树。二叉堆有两个类型：最大堆 和 最小堆。

二叉堆

最大堆

最大堆：任何一个父节点的值，都 大于 或 等于 它左、右子节点的值，堆顶 是整个堆中的 最大 元素。

最小堆

最小堆：任何一个父节点的值，都 小于 或 等于 它左、右孩子节点的值，堆顶 是整个堆中的 最小 元素。

二叉堆的操作

二叉堆的操作主要有 插入、删除、构建 三种操作。二

二叉堆的操作都基于堆的 自我调整 。所谓堆的自我调整，就是把一个不符合堆性质的完全二叉树，通过上浮 或 下沉 的方式调整成一个堆。

二叉堆 是实现 堆排序 及 优先队列 的基础。

插入节点

从末尾插入节点，插入的节点和需要和父节点进行比较：

• 如果是最大堆，插入节点大于父节点，插入节点上浮直到小于父节点不上浮。

• 如果是最小堆，插入节点小于父节点，插入节点上浮直到大于父节点不上浮。

删除节点

删除节点和插入节点的过程正好相反，所删除的是处于堆顶的节点。

删除堆顶节点，把堆的最后一个元素补充到堆顶的位置，然后于左、右子节点比较，根据是最大堆或最小堆来判断是否下沉。

构建二叉堆

构建二叉堆，就是把一个无序的完全二叉树调整为二叉堆，本质是让所有 非叶子节点依次 “下沉”。

非叶子节点与左、右子节点比较，根据最大堆或最小堆来决定是否下沉。

堆的插入操作是插入节点的上浮，删除操作是插入节点的下沉。

这两个操作的平均交换次数都是堆高度的一半，所以时间复杂度是 Ο(logn) ，而构建堆的时间复杂度是 Ο(n) 。

二叉堆代码实现

二叉堆虽然是一个完全二叉树，但存储方式是顺序存储，而不是链式存储。在存储的物理结构上是采用数组存储。

一个数组中，在没有左、右指针的情况下，首先将数组最后一个元素(right = array.length - 1) 作为最后的叶子节点，再确定一个父节点的下标（parent = (right - 1) / 2），那它的左节点就是 left = parent 2 + 1，右子节点就是 right = parent 2 + 2 。

package com.datastructure.alg.binaryheap;

import java.util.Arrays;

/**
 * 二叉堆创建与操作
 */
public class BinaryHeap {

    /**
     * 下沉 调整
     *
     * @param array       待调整的堆
     * @param parentIndex 父节点索引
     * @param length      堆大小
     */
    public static void downAdjust(int[] array, int parentIndex, int length) {
        //保存父节点值，用于最后赋值
        int temp = array[parentIndex];
        int childIndex = 2 * parentIndex + 1;
        while (childIndex < length) {
            //如果有右子节点，且右子节点小于左子节点的值，则定位到右子节点
            if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
                childIndex++;
            }

            if (temp <= array[childIndex]) {
                break;
            }

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

    /**
     * 构建堆
     *
     * @param array
     */
    public static void buildHeap(int[] array) {

        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            //数组取半求父节点的索引 -1, 给最后的右页子节点留位置 -1, 
            //从最后一个非叶子节点开始，做依次下沉调整
            downAdjust(array, i, array.length);
            System.out.println("遍历：" + Arrays.toString(array));
    }
    }

    public static void main(String[] args) {
        int[] array = new int[]{4, 2, 11, 10, 8, 3, 9, 1, 5, 6, 7};
        System.out.println("原始：" + Arrays.toString(array));
        buildHeap(array);
        System.out.println("最终：" + Arrays.toString(array));
        //最终：[1, 2, 3, 4, 6, 11, 9, 10, 5, 8, 7]
    }
}

优先队列

队列的特点是先进先出（FIFO）。入队列，将新元素置于队尾；出队列，队头元素最先被移出。

特点

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

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

例如，有一个最大优先队列，可能最大元素并不是队头元素，但出队时仍然是此最大元素首先出队。

基于二叉堆的特性，即最大堆的堆顶是整个堆中的最大元素，最小堆的堆顶是整个堆中的最小元素。

因此，可以用最大堆来实现最大优先队列，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。

入队

入队：就是插入节点的操作，在堆的末尾插入，与父节点比较，大于则上浮到合适位置。

出队

出队：就是堆顶节点的删除操作，然后把最后一个节点替换到堆顶位置，再与左、右子节点比较，如果子节点更大则上浮。

二叉堆节点 上浮 和 下沉 的时间复杂度都是 Ο(logn) ，所以优先队列入队和出队的时间复杂度也是 Ο(logn) 。

代码实现

import java.util.Arrays;

public class PriorityQueue {

    private int[] array;
    private int size;

    public PriorityQueue() {
        //队列初始长度为 32
        this.array = new int[32];
    }

    /**
     * 入队
     *
     * @param key
     */
    public void enQueue(int key) {
        if (size >= array.length) {
            resize();
        }
        array[size++] = key;
        upAdjust();
    }

    /**
     * 出队
     */
    public int deQueue() throws Exception {
        if (size <= 0) {
            throw new Exception("the queue is empty");
        }

        //获取堆顶元素
        int head = array[0];
        //让最后一个元素移动到堆顶
        array[0] = array[--size];
        downAdjust();
        return head;
    }

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

    }

    /**
     * 下沉调整
     */
    private void downAdjust() {
        int parentIndex = 0;
        int temp = array[parentIndex];
        int childIndex = 1;
        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 * childIndex + 1;
        }
        array[parentIndex] = temp;
    }

    /**
     * 队列扩容
     */
    private void resize() {
        //队列容量翻倍
        int newSize = this.size * 2;
        this.array = Arrays.copyOf(this.array, newSize);
    }

    public static void main(String[] args) throws Exception {
        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.enQueue(3);
        priorityQueue.enQueue(5);
        priorityQueue.enQueue(10);
        priorityQueue.enQueue(2);
        priorityQueue.enQueue(7);

        System.out.println("出队元素：" + priorityQueue.deQueue());
        System.out.println("出队元素：" + priorityQueue.deQueue());
    }
}

更多参考

1. 二叉堆(三)之 Java的实现 。
2. 数据结构与算法系列 目录 此系列博文非常不错。