定义
堆(heap)也被称为优先队列(priority queue)。是一种特殊的树状数据结构。
普通队列是先进先出(first in first out)，而优先队列出栈的顺序是按照元素的优先权大小。
堆可以分为”大顶堆“也称”最大堆“（最大值优先出列），”小顶堆“也称”最小堆“（最小值优先出列）。
![]()
堆的常用方法：
实现
堆是用数组实现的完全二叉树。目前有多种算法可以实现堆，速度最快的是斐波那契堆。
![]()
具体的实现可以参考一下这两篇文章
Learning to Love Heaps
Heap
使用
LeetCode第703题Kth Largest Element in a Stream
)就是一个使用堆的场景，如果我们使用简单的数组排序的方法很有可能超时，使用堆是该题的最优解之一。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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
