数据结构之堆

思考

假如需要设计一种数据结构，用来存放整数，要求提供3个接口：

• 添加元素
• 获取最大值
• 删除最大值

如果使用动态数组、双向链表和二叉树实现这个数据结构对应的时间复杂度如下表所示：

	添加元素	获取最大值	删除最大值	说明
动态数组\双向链表	O(1)	O(n)	O(n)
有序动态数组\双向链表	O(n)	O(1)	O(1)	全排序有点浪费
平衡二叉搜索树	O(logn)	O(logn)	O(logn)	杀鸡焉用牛刀

有没有更优的数据结构？使用堆，可以使得获取最大值的时间复杂度为O(1)、删除最大值和添加元素的时间复杂度为O(logn)。

堆的介绍

堆（Heap）也是一种树状的数据结构（不要跟java内存模型中的“堆空间”混淆），常见的堆实现有：

• 二叉堆（Binary Heap，完全二叉堆）
• 多叉堆（D-heap、D-ary Heap）
• 索引堆（Index Heap）
• 二项堆（Binomial Heap）
• 斐波那契堆（Fibonacci Heap）
• 左倾堆（Leftist Heap，左式堆）
• 斜堆（Skew Heap）

本文中主要介绍的是二叉堆。

堆的性质：任意节点的值总是 ≥（ ≤ ）子节点的值

• 如果任意节点的值总是 ≥ 子节点的值，称为：最大堆、大根堆、大顶堆
• 如果任意节点的值总是 ≤ 子节点的值，称为：最小堆、小根堆、小顶堆

由此可见，堆中的元素必须具备可比较性（跟二叉搜索树一样）。

二叉堆（Binary Heap）

二叉堆的逻辑结构就是一棵完全二叉树，所以也叫完全二叉堆。

鉴于完全二叉树的一些特性，二叉堆的底层（物理结构）一般用数组实现即可。

数组中索引i的规律（n是元素数量）：

• 如果 i = 0 ，它是根节点
• 如果 i > 0 ，它的父节点的索引为 floor( (i – 1) / 2 )
• 如果 2i + 1 ≤ n – 1，它的左子节点的索引为 2i + 1
• 如果 2i + 1 > n – 1 ，它无左子节点
• 如果 2i + 2 ≤ n – 1 ，它的右子节点的索引为 2i + 2
• 如果 2i + 2 > n – 1 ，它无右子节点

堆的接口设计

public interface Heap<E> {

    int size();

    boolean isEmpty();

    void clear();

    E get();

    void add(E e);

    E replace(E e);

    E remove();
}

堆的数据结构

public class BinaryHeap<E> implements Heap<E> {

    private int size;

    private E[] elements;

    public static final int DEFAULT_CAPACITY = 10;

    private Comparator<E> comparator;

    public BinaryHeap() {
        this(null, null);
    }

    public BinaryHeap(Comparator<E> comparator) {
        this.comparator = comparator;
        this.elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

添加元素

将添加的节点加入到数组最后位置，然后循环执行以下操作（图中的80简称为node）

• 如果 node ＞ 父节点，与父节点交换位置
• 如果 node ≤ 父节点，或者 node 没有父节点，退出循环

这个过程，叫做上滤（Sift Up），时间复杂度：O(logn)

代码实现如下：

    public void add(E e) {
        elementEmptyCheck(e);

        elements[size] = e;
        siftUp(size);
        size++;
    }

    private void elementEmptyCheck(E e) {
        if(null == e) {
            throw new IllegalArgumentException("Element must not be null");
        }
    }

    /**
     * 从index开始上滤
     * @param index
     */
    private void siftUp(int index) {
        E element = elements[index];
        while (index > 0) {
            int parentIndex = index >> 1;
            E parentElement = elements[parentIndex];

            if(compare(element, parentElement) <= 0) {
                break;
            }

            elements[index] = parentElement;
            index = parentIndex;
        }
        elements[index] = element;
    }

    private int compare(E e1, E e2) {
        if(null != comparator) {
            return comparator.compare(e1, e2);
        }
        return ((Comparable) e1).compareTo(e2);
    }

删除元素

删除的步骤如下

1. 用最后一个节点覆盖根节点
2. 删除最后一个节点
3. 循环执行以下操作（图中的43简称为node）
   • 如果 node < 最大的子节点，与最大的子节点交换位置
   • 如果 node ≥ 最大的子节点， 或者 node 没有子节点，退出循环

这个过程，叫做下滤（Sift Down），时间复杂度：O(logn)

删除操作的代码实现如下：

   public E remove() {

        int lastIndex = --size;

        E element = elements[0];

        elements[0] = elements[lastIndex];
        elements[lastIndex] = null;

        siftDown(0);

        return element;
    }

    /**
     * 从index开始下滤
     * @param index
     */
    private void siftDown(int index) {
        E element = elements[index];
        int half = size >> 1;
        while (index < half) { // index必须是非叶子节点

            int childIndex = (index << 1) + 1;
            E child = elements[childIndex];

            if(childIndex + 1 < size) {
                if(compare(child, elements[childIndex + 1]) < 0) {
                    childIndex = childIndex+1;
                    child = elements[childIndex];
                }
            }

            if(compare(element, child) > 0) {
                break;
            }

            elements[index] = child;

            index = childIndex;
        }
        elements[index] = element;
    }

替换元素

用新元素替换最大值（第一个元素），操作过程类似删除。

替换操作的代码实现如下：

    @Override
    public E replace(E e) {
        elementEmptyCheck(e);

        if(isEmpty()) {
            elements[size++] = e;
            return null;
        }

        E oldValue = elements[0];
        elements[0] = e;
        siftDown(0);
        return oldValue;
    }

构建小顶堆

小顶堆无需新建类，只需要在BinaryHeap的构造方法中，修改一下Comparator的比较策略即可。

可以使用下面的代码构造大顶堆：

BinaryHeap<Integer> binaryHeap = new BinaryHeap<>((o1, o2) -> o1 - o2);

可以使用下面的代码构造小顶堆：

BinaryHeap<Integer> binaryHeap = new BinaryHeap<>((o1, o2) -> o2 - o1);

更多精彩内容关注本人公众号：架构师升级之路

本文地址：https://blog.csdn.net/u022812849/article/details/107038143