数据结构学习笔记 - 09 堆和优先队列

优先队列介绍

优先队列也是一个队列，因此也适用于之前实现的队列接口。不过优先队列出队永远需要优先级对高的。

优先队列针对的是动态的情况，如果是静态的，那么只需要排序一次即可。

依然可以使用之前实现普通队列的方式实现优先队列，即使用数组或链表这样的线性结构实现优先队列。只不过无法再像实现普通队列那样，使入队和出队的复杂度都为 O(1)。

使用堆来实现优先队列，可以使得入队和出队操作都为 O(logn) 级别。

	入队	出队
专门维护一个顺序的线性结构，即入队时进行排序	O(n)	O(1)
普通队列出队操作时遍历找到优先级最高的元素	O(1)	O(n)
使用堆实现	O(logn)	O(logn)

堆的介绍

• 满二叉树，除最后一层无任何叶子节点外，其所有非叶子节点均既有左孩子又有右孩子。
• 完全二叉树，其不一定是一颗满二叉树，但是其不满的部分一定是在树的右下侧。也就是除了最底层之外，上面的是一个满二叉树，最底层从左开始放置元素。
• 二叉堆就是一个完全二叉树。
• 最大堆：堆中某个节点的值总是不大于其父节点的值（相应也有最小堆）。需要注意的是，这个定义没有要求较下层的某个节点一定不会大于较上层的所有节点。

对于完全二叉树来说，通过层序遍历，可以将节点放入一个数组中。实际上堆的存储结构也是使用一个数组最为合适。

当使用一个数组表示一个堆的时候，根节点放在第一个位置，索引为 0。假如某节点索引为 i，其左孩子节点索引就是 2i + 1，右孩子节点索引就是 2i + 2，其父节点索引就是 (i - 1) / 2。如果为了表示方便，也可以空一个位置，将根节点放在索引为 1 的位置，那么假如某节点索引为 i，其左孩子节点索引就是 2i，右孩子节点索引就是 2i + 1，其父节点索引就是 i / 2。

根节点索引	当前节点索引	左孩子索引	右孩子索引	父节点索引
0	i	2i + 1	2i + 2	(i - 1) / 2
1	i	2i	2i + 1	i / 2

对于完全二叉树，寻找最后一个非叶子节点的索引就是找最后一个节点的父亲节点。

复杂度

操作	复杂度
add	O(logn)
extractMax	O(logn)
findMax	O(1)
replace	O(logn)
heapify	O(n)

其中，add 操作的步骤是先将元素添加到队尾，之后使用 sift up 操作，即不断和其父节点做比较，如果其大于父节点元素就两者互换，这个操作的复杂度是 O(logn)。extractMax 操作的步骤是先获取队首最大元素，之后将队尾元素放到队首，移除队尾多余的空位后，将换到队首的那个元素使用 sift down 操作，这个复杂度也是 O(logn)。

replace 操作是使用一个新元素替换掉队首的最大元素，可以使用 add 操作之后接一个 extractMax 操作来实现，但是这样的话复杂度就是两个 O(logn) 操作。所以可以专门给它一个优化实现，就是使用新元素直接替换队首元素位置，之后将新元素做 sift down 操作，这样复杂度就是一个 O(logn)。

heapify 操作是将一个任意数组转为一个堆的过程。具体实现是先将这个数组看作一个完全二叉树，之后从最后一个非叶子节点开始逐渐向前进行 sift down 操作。如果将 n 个元素逐个插入到一个空堆中，复杂度是 O(nlogn) 级别的。但是 heapify 的过程，算法复杂度其实是 O(n) 级别的（这个复杂度先记住就好）。

堆的实现

使用动态数组实现一个最大堆：

public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;

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

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

    /**
     * 将任意一个数组生成为一个最大堆。
     * 如果将 n 个元素逐个插入到一个空堆中，复杂度是 O(nlogn) 级别的。
     * heapify 的过程，算法复杂度是 O(n) 级别的
     */
    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 doesn't have parent.");
        }
        return (index - 1) / 2;
    }

    /**
     * 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引。
     */
    private int leftChild(int index) {
        return index * 2 + 1;
    }

    /**
     * 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引。
     */
    private int rightChild(int index) {
        return index * 2 + 2;
    }

    /**
     * 向堆中添加元素
     */
    public void add(E e) {
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }

    /**
     * 元素堆上浮，新添加一个元素后，需要不断和它堆父节点做比较，如果大了就上浮
     * 
     * @param k 需要上浮元素的索引
     */
    private void siftUp(int k) {

        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
            data.swap(k, parent(k));
            k = parent(k);
        }
    }

    /**
     * 看堆中的最大元素，不取出。
     */
    public E findMax() {
        if (data.getSize() == 0) {
            throw new IllegalArgumentException("Can not findMax when heap is empty.");
        }

        return data.get(0);
    }

    /**
     * 取出堆中最大元素。复杂度 O(logn)
     * 对于堆来讲，我们只能拿最大堆也就是根节点，或者说数组索引为 0 的元素。
     */
    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 j = leftChild(k);
            if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
                j = rightChild(k);
            }

            if (data.get(k).compareTo(data.get(j)) >= 0) {
                break;
            }

            data.swap(k, j);
            k = j;
        }
    }

    /**
     * 取出堆中最大的元素，并且替换成元素 e
     * 正常情况下，这是两个操作，即先 extractMax，再 add，复杂度就是连续两个 O(logn)
     * 但是组合起来就可以直接用新元素替换旧元素，然后再 siftDown,复杂度就仅仅是 O(logn)
     */
    public E replace(E e) {
        E ret = findMax();
        data.set(0, e);
        siftDown(0);

        return ret;
    }
}

优先队列的实现

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 E getFront() {
        return maxHeap.findMax();
    }

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

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

更多

关于堆：

我们实现的是二叉堆，相应的也就有三叉堆、四叉堆等等。对于 d叉堆来说，层数有可能更少，这在有些操作上会让速度更快。但是比如下沉操作，就要考虑 d 个子节点而不是 2 个。

另外，更高级的堆还有如索引堆（它可以操作堆中的某个元素）、二项堆、斐波那契堆等。

关于队列：

如果从广义上讲，能满足的队列接口的数据结构就可以成为队列。那么除了普通的队列，优先队列之外，其实栈也可以被理解是一个队列。当我们这么理解的时候，就会发现，之前使用栈辅助实现二分搜索树的前序遍历，使用队列辅助实现二分搜索树的层序遍历，他们在逻辑上是一致的。