定义
堆(heap)也被称为优先队列(priority queue)。是一种特殊的树状数据结构。
普通队列是先进先出(first in first out)，而优先队列出栈的顺序是按照元素的优先权大小。
堆可以分为”大顶堆“也称”最大堆“（最大值优先出列），”小顶堆“也称”最小堆“（最小值优先出列）。
MinHeapAndMaxHeap.png
堆的常用方法：
- 构建优先队列
- 快速找出最大值(最小值)
实现
堆是用数组实现的完全二叉树。目前有多种算法可以实现堆，速度最快的是斐波那契堆。
堆的实现算法
具体的实现可以参考一下这两篇文章
使用
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();
}
}
