DS07:堆与优先队列

堆的基本概念

堆（二叉堆）就是用数组实现的二叉树（完全二叉树），所以它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置。

堆的用处

• 构建优先队列
• 支持堆排序（O(n log n)）
• 快速找出一个集合中的最小值（或者最大值）

堆属性

堆可以分为最大堆与最小堆等等，差别只在于节点的排序方法。

以最大堆为例，堆中某个节点的值总是不大于其父亲节点的值 。也就是说，最大堆总将最大的值放在树的根节点（也就是数组索引为0的位置）。根据堆的这一特性，堆能够作为优先队列的实现。

注意：堆的根节点中存放的是最大或者最小元素，但是其他节点的排序顺序是未知的。例如，在一个最大堆中，最大的那一个元素总是位于 index 0 的位置，但是最小的元素则未必是最后一个元素。–唯一能够保证的是最小的元素是一个叶节点，但是不确定是哪一个。

堆与普通树的区别

节点的顺序。在二叉搜索树中，左子节点必须比父节点小，右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。且以最大堆举例，最下层的节点值未必一定小于上层节点的值

内存占用。普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配内存。堆仅仅使用一个数组来存储数据，且不使用指针。

平衡。二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足堆属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。

搜索。在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。

堆的实现

实现基础

堆的底层可以使用动态数组进行实现，由于完全二叉树的特性，按照层序遍历对二叉树进行存储时父节点与子节点之间有以下的规律：

parent = i/2	// i为子节点在数组中的索引

leftChild = 2 * i + 1	// i为父节点

rightChild = 2 * i+ 2

因此可基于之前实现的动态数组进行最大堆的基本实现：

public class MaxHeap<E extends Comparable> {
    private Array<E> data;
    public MaxHeap(int capacity) {
        data = new Array<>(capacity);
    }

    public MaxHeap() {
        data = new Array<>();
    }

    public MaxHeap(E[] arr) {
        data = new Array<>(arr);
        for (int i=parent(arr.length - 1); i>=0; i--) {
            siftDown(i);
        }
    }

    public int size() {
        return data.getSize();
    }

    public boolean isEmpty() {
        return data.isEmpty();
    }

	// 获得父节点索引
    private int parent(int index) {
        if(index == 0) {
            throw new IllegalArgumentException("Index 0 has no parent");
        }
        return (index - 1) / 2;
    }

	// 获得左子节点索引
    private int leftChild(int index) {
        return index * 2 + 1;
    }

	// 获得右子节点索引
    private int rightChild(int index) {
        return index * 2 + 2;
    }

}

添加元素

向堆中添加元素首先将元素添加到数组最后，之后进行堆的上浮操作。

即当该元素的父节点值 < 该元素值时：将这两个元素进行交换，知道到达根节点或不满足该条件。详见代码，复杂度为O(log n)。

// 添加元素
public void add(E e) {
    data.addLast(e);
    shiftUp(data.getSize() - 1);
}

// 堆的上浮
private void shiftUp(int k) {
    while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ) {
        data.swap(k, parent(k));
        k = parent(k);
    }
}

取出堆中最大元素

将第一个元素取出后，将最后一个元素放入根节点的位置（即将索引为0 与 索引为 size-1的元素互换），再进行堆的下沉的操作。

堆的下沉即为，如果当前节点小于其子节点中最大的那个，则将其替换。详见代码，复杂度为O(log n)

// 返回堆中最大元素
public E findMax() {
    if(data.getSize() == 0) {
        throw new IllegalArgumentException("heap is empty");
    }
    return data.getFirst();
}

// 取出堆中最大元素
public E extractMax() {
    E ret = findMax();
    data.swap(0, data.getSize()-1);
    data.removeLast();
    siftDown(0);
    return ret;
}

// 堆的下浮
private void siftDown(int k) {
    while (leftChild(k) < data.getSize()) {
        int maxChild = leftChild(k);
        if(maxChild +1 < data.getSize() && data.get(maxChild +1).compareTo(data.get(maxChild)) > 0) {
            maxChild++;
        }
        if(data.get(k).compareTo(data.get(maxChild)) >= 0){
            break;
        }
        data.swap(k, maxChild);
        k = maxChild;
    }
}

将输入数组变为堆（heapify）

将输入数组变为堆结构，首先找到最后一个非叶子节点（即最后一个叶子节点的父节点），之后向前遍历，并分别进行下沉操作，如代码所示（作为maxHeap类的构造函数）

这样做的好处是时间复杂度只有O(n)，而将数组元素分别插入进堆的时间复杂度为O(n log n)

public MaxHeap(E[] arr) {
    data = new Array<>(arr);
    for (int i=parent(arr.length - 1); i>=0; i--) {
        siftDown(i);
    }
}

优先队列

优先队列也就是优先级最大的元素在队首的队列了，显而易见，其可以使用堆轻松实现，下面是简单的最大值在前的优先队列。

public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

    private MaxHeap<E> maxHeap;

    public PriorityQueue() {
        maxHeap = new MaxHeap<>();
    }

    @Override
    public int getSize() {
        return maxHeap.size();
    }

    @Override
    public boolean isEmpty() {
        return maxHeap.isEmpty();
    }

    @Override
    public void enqueue(E e) {
        maxHeap.add(e);
    }

    @Override
    public E dequeue() {
        return maxHeap.extractMax();
    }

    @Override
    public E getFront() {
        return maxHeap.findMax();
    }
}

参考链接：

https://www.jianshu.com/p/6b526aa481b1

Donate