堆（优先队列）

定义

堆(heap)也被称为优先队列(priority queue)。是一种特殊的树状数据结构。

普通队列是先进先出(first in first out)，而优先队列出栈的顺序是按照元素的优先权大小。

堆可以分为”大顶堆“也称”最大堆“（最大值优先出列），”小顶堆“也称”最小堆“（最小值优先出列）。

MinHeapAndMaxHeap.png

堆的常用方法：

• 构建优先队列
• 快速找出最大值(最小值)

实现

堆是用数组实现的完全二叉树。目前有多种算法可以实现堆，速度最快的是斐波那契堆。

堆的实现算法

具体的实现可以参考一下这两篇文章

Learning to Love Heaps
Heap

使用

LeetCode第703题Kth Largest Element in a Stream就是一个使用堆的场景，如果我们使用简单的数组排序的方法很有可能超时，使用堆是该题的最优解之一。

class KthLargest {
    private final PriorityQueue<Integer> q;
    private final int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        q = new PriorityQueue<>(k);
        for (int n : nums) {
            add(n);
        }
    }

    public int add(int val) {
        if (q.size() < k) {
            q.offer(val);
        } else if (q.peek() < val) {
            q.poll();
            q.offer(val);
        }
        return q.peek();
    }
}

参考资料

Heap wiki
Learning to Love Heaps
Heap
Heap Data Structure