二叉堆

二叉堆

二叉堆本质上是一棵完全二叉树，完全二叉树的叶子节点都排列在树的左边，体现出一种顺序的关系。
正是因为有了连续性，我们可以用数组来表示一个二叉堆。
二叉堆实现的大顶堆有一个非常重要的特性：堆中某个节点的值不会大于其父节点。
反之：小顶堆堆中某个节点的值不会小于其父节点。

二叉堆的表示

数组索引从 1 开始

堆是用数组来表示的，根据图中的公式，父亲节点很容易找到子节点，子节点也很容易找到父亲节点。

数组索引从 0 开始

大顶堆代码实现（基础架构）

/**
 * 最大堆实现
 *
 * @param <E> 泛型，支持多种对象
 */
public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;
    public MaxHeap(int capacity) {
        this.data = new Array<>(capacity);
    }
    public MaxHeap() {
        this.data = new Array<>();
    }
    public int size() {
        return data.getSize();
    }
    public boolean isEmpty() {
        return data.isEmpty();
    }
    /**
     * 数组索引从 0 开始
     *
     * @param index 当前索引
     * @return 父亲节点索引
     */
    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        }
        return (index - 1) / 2;
    }
    /**
     * @param index 当前索引
     * @return 左孩子的索引
     */
    private int leftChild(int index) {
        return index * 2 + 1;
    }
    /**
     * @param index 当前索引
     * @return 右孩子的索引
     */
    private int rightChild(int index) {
        return index * 2 + 2;
    }
}

向堆中插入元素

因为二叉堆内部实现依赖于数组，所以新插入一个元素，肯定在数组的末尾的位置。
当元素插入到数组的末尾位置，假设这个元素的值很大，不符合二叉堆的性质（父亲节点大于子节点），所以这个新插入的节点需要上浮操作，调整到合适的位置，以满足二叉堆的特征。
上浮流程相对简单，每次与父亲节点比较，父亲节点的值比它小，就交换元素，继续上浮，直到父亲节点比它大或者它已经调整到了根节点。
下面用图片演示一遍：

插入元素代码实现

/**
 * 增加元素
 *
 * @param e e
 */
public void add(E e) {
    data.addLast(e);
    siftUp(data.getSize() - 1);
}
/**
 * 上浮操作
 *
 * @param index 当前索引
 */
private void siftUp(int index) {
    // index == 0，说明已经到了根节点了
    while (index > 0 && data.get(parent(index)).compareTo(data.get(index)) < 0) {
        data.swap(index, parent(index));
        // 更新当前索引，继续上浮
        index = parent(index);
    }
}

取出堆中最大元素

取出堆中最大元素，其实就是取出数组索引为 0 对应的值，这是由二叉堆的特性决定的，根节点元素大于所有的子节点元素。
取走了堆顶元素，我们必须指定一个新的节点作为新的堆顶节点。一般的做法是把数组的最后一位元素放在堆顶，然后将这个元素进行下沉操作，调整到合适的位置。
上面就是取出堆中最大元素的操作流程，总体上是比较清晰的。但是在实现上，我们要把父节点和左右两个子节点都进行比较，且右孩子节点不能越界。

/**
 * @return 堆顶元素
 */
public E findMax() {
    if (data.getSize() == 0) {
        throw new IllegalArgumentException("Can not find Max when heap is empty");
    }
    return data.get(0);
}
/**
 * 返回堆顶元素，并维护二叉堆的特性
 *
 * @return 返回堆顶元素
 */
private E extractMax() {
    final E max = findMax();
    // 第一个元素和最后一个元素互换位置
    data.swap(0, data.getSize() - 1);
    // 删除最后一个元素
    data.removeLast();
    // 下沉操作，从堆顶开始
    siftDown(0);
    return max;
}
/**
 * 下沉操作
 *
 * @param k 索引
 */
private void siftDown(int k) {
    while (leftChild(k) < data.getSize()) {
        int j = leftChild(k);
        // 比较左右孩子，谁大谁小
        if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
            j++;
        }
        // 比较父节点与子节点，父节点大于最大的子节点，满足二叉堆的特性，退出循环
        if (data.get(k).compareTo(data.get(j)) >= 0) {
            break;
        }
        data.swap(k, j);
        k = j;
    }
}