数据结构之堆

数据结构之堆

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

  • 添加元素
  • 获取最大值
  • 删除最大值
    如果使用动态数组、双向链表和二叉树实现这个数据结构对应的时间复杂度如下表所示:
    image.png
    有没有更优的数据结构?使用堆,可以使得获取最大值的时间复杂度为O(1)、删除最大值和添加元素的时间复杂度为O(logn)。

堆的介绍
堆(Heap)也是一种树状的数据结构(不要跟java内存模型中的“堆空间”混淆),常见的堆实现有:

  • 二叉堆(Binary Heap,完全二叉堆)

  • 多叉堆(D-heap、D-ary Heap)

  • 索引堆(Index Heap)

  • 二项堆(Binomial Heap)

  • 斐波那契堆(Fibonacci Heap)

  • 左倾堆(Leftist Heap,左式堆)

  • 斜堆(Skew Heap)
    本文中主要介绍的是二叉堆。
    image.png
    堆的性质:任意节点的值总是 ≥( ≤ )子节点的值

  • 如果任意节点的值总是 ≥ 子节点的值,称为:最大堆、大根堆、大顶堆

  • 如果任意节点的值总是 ≤ 子节点的值,称为:最小堆、小根堆、小顶堆
    由此可见,堆中的元素必须具备可比较性(跟二叉搜索树一样)。

二叉堆(Binary Heap)
二叉堆的逻辑结构就是一棵完全二叉树,所以也叫完全二叉堆。

鉴于完全二叉树的一些特性,二叉堆的底层(物理结构)一般用数组实现即可。
image.png
数组中索引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];
    }

添加元素

image.png
将添加的节点加入到数组最后位置,然后循环执行以下操作(图中的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);
    }

删除元素

image.png
删除的步骤如下

  • 用最后一个节点覆盖根节点
  • 删除最后一个节点
  • 循环执行以下操作(图中的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 binaryHeap = new BinaryHeap<>((o1, o2) -> o1 - o2);
1
可以使用下面的代码构造小顶堆:

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