堆2：堆的应用
优先队列
堆非常适合用来实现优先队列。优先队列每次取出都是优先级最高的元素，十分契合堆的性质。
下面是Java的PriorityQueue的向下堆化与向上堆化实现
/**
* Inserts item x at position k, maintaining heap invariant by * promoting x up the tree until it is greater than or equal to * its parent, or is the root. * * To simplify and speed up coercions and comparisons, the * Comparable and Comparator versions are separated into different * methods that are otherwise identical. (Similarly for siftDown.) * * @param k the position to fill
* @param x the item to insert
*/private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x, queue, comparator);
else siftUpComparable(k, x, queue);
}
private static <T> void siftUpComparable(int k, T x, Object[] es) {
Comparable<? super T> key = (Comparable<? super T>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = es[parent];
if (key.compareTo((T) e) >= 0)
break;
es[k] = e;
k = parent;
}
es[k] = key;
}
private static <T> void siftUpUsingComparator(
int k, T x, Object[] es, Comparator<? super T> cmp) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = es[parent];
if (cmp.compare(x, (T) e) >= 0)
break;
es[k] = e;
k = parent;
}
es[k] = x;
}
/**
* Inserts item x at position k, maintaining heap invariant by * demoting x down the tree repeatedly until it is less than or * equal to its children or is a leaf. * * @param k the position to fill
* @param x the item to insert
*/private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x, queue, size, comparator);
else siftDownComparable(k, x, queue, size);
}
private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
// assert n > 0;
Comparable<? super T> key = (Comparable<? super T>)x;
int half = n >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; // assume left child is least
Object c = es[child];
int right = child + 1;
if (right < n &&
((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
c = es[child = right];
if (key.compareTo((T) c) <= 0)
break;
es[k] = c;
k = child;
}
es[k] = key;
}
private static <T> void siftDownUsingComparator(
int k, T x, Object[] es, int n, Comparator<? super T> cmp) {
// assert n > 0;
int half = n >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = es[child];
int right = child + 1;
if (right < n && cmp.compare((T) c, (T) es[right]) > 0)
c = es[child = right];
if (cmp.compare(x, (T) c) <= 0)
break;
es[k] = c;
k = child;
}
es[k] = x;
}
/**
* Establishes the heap invariant (described above) in the entire tree, * assuming nothing about the order of the elements prior to the call. * This classic algorithm due to Floyd (1964) is known to be O(size). */private void heapify() {
final Object[] es = queue;
int n = size, i = (n >>> 1) - 1;
final Comparator<? super E> cmp;
if ((cmp = comparator) == null)
for (; i >= 0; i--)
siftDownComparable(i, (E) es[i], es, n);
else for (; i >= 0; i--)
siftDownUsingComparator(i, (E) es[i], es, n, cmp);
}合并文件
假设有N个有序的csv小文件，里面有每一行都是一个身份信息，第一个单元格的数据都是身份证信息，现要求将n个文件合并成一个大文件，要求同一个地区的身份信息放在一起。
由于原本的小文件是有序的，此时我们可以构建一个优先队列（堆），首先取出每个文件的第一行数据，加入队列。每次取出队列首位（堆顶元素），放入到大文件，然后再从该元素的来源小文件取出下一行，加入到队列。依此类推就可以一步步将文件有序合并到一个大文件。思路上和归并排序类似。
定时任务
假设我们有N个待处理的定时任务，他们的执行时间都不一样。那么我们可以将任务放入优先队列(堆)，执行器计算出堆顶任务的执行时间与当前时间的差值T，在休眠时间T后再取出堆顶任务执行。依此类推，每次执行都可以计算出更加准确的休眠T信息，这样就比定时轮询更加高效。
TOP K 问题
Top K在实际应用中，常常被用来做热搜榜之类的排名。思路是维护一个K大小的优先队列（堆），然后每次比较堆顶元素，如果比堆顶大，则将该元素放入到队列中。我们依次取出堆顶元素，就可以构建热搜Top K。
Top K 问题有许多变体，我们都可以用堆解决
下面的问题的解法都用到了[[堆1：堆与堆排序]]中堆的实现
数组中的第K个最大元素
问题描述如下：
给定整数数组 `nums` 和整数 `k`，请返回数组中第 `**k**` 个最大的元素。
请注意，你需要找的是数组排序后的第 `k` 个最大的元素，而不是第 `k` 个不同的元素。
你必须设计并实现时间复杂度为 `O(n)` 的算法解决此问题。
**示例 1:**
**输入:** `[3,2,1,5,6,4],` k = 2
**输出:** 5
**示例 2:**
**输入:** `[3,2,3,1,2,4,5,5,6],` k = 4
**输出:** 4
可构建一个大小为k的小顶堆，先将k个元素放入到堆中，然后，如果后续元素大于堆顶元素则移除堆顶元素，将该元素放入。最终堆顶元素就是第k个最大元素
public static Integer resolve (Integer[] nums,int k) {
Heap<Integer> heap = new Heap<>(k);
int i = 0;
for (Integer num : nums) {
if(i < k){
heap.add(num);
}else {
// 最小元素小于当前元素则替换掉该元素
if (heap.top().compareTo(num) < 0){
heap.removeTop();
heap.add(num);
}
}
i++;
}
return heap.top();
}堆化时间复杂度是logK，需要循环n次，时间复杂度是O(nlogK)。
前 K 个高频元素
问题描述如下：
给你一个整数数组 `nums` 和一个整数 `k` ，请你返回其中出现频率前 `k` 高的元素。你可以按 **任意顺序** 返回答案。
**示例 1:**
**输入:** nums = [1,1,1,2,2,3], k = 2
**输出:** [1,2]
**示例 2:**
**输入:** nums = [1], k = 1
**输出:** [1]
**提示：**
- `1 <= nums.length <= 105`
- `k` 的取值范围是 `[1, 数组中不相同的元素的个数]`
- 题目数据保证答案唯一，换句话说，数组中前 `k` 个高频元素的集合是唯一的思路是先遍历一遍记录每个词的出现频率，构建堆元素，然后构建一个K大小的小顶堆，先将k个元素放入到堆中，然后，如果后续元素大于堆顶元素则移除堆顶元素，将该元素放入。依次取出堆中元素就是top k 高频元素。
static class Item<T> implements Comparable<Item<T>>{
T data;
int count;
@Override
public int compareTo(Item<T> o) {
return count - o.count;
}
}
public static Integer[] resolve (Integer[] nums,int k) {
Integer[] res = new Integer[k];
// 先统计
HashMap<Integer,Item<Integer>> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
Integer num = nums[i];
Item<Integer> defaultV = new Item<>();
defaultV.data = num;
defaultV.count = 0;
Item<Integer> v = map.getOrDefault(num, defaultV);
v.count++;
map.put(num,v);
}
Heap<Item<Integer>> heap = new Heap<>(k);
int i = 0;
for (Item<Integer> value : map.values()) {
if(i < k){
heap.add(value);
}else {
// 最小元素小于当前元素则替换掉该元素
if (heap.top().compareTo(value) < 0){
heap.removeTop();
heap.add(value);
}
}
i++;
}
for (int j = 0; j < k; j++) {
res[j] = heap.removeTop().data;
}
return res;
}遍历统计词时间是n；建堆时间是logK，需要遍历n次；取出元素时间为k，所以时间为n + nlogK + k 时间复杂度是O(nlogK)
中位数问题
问题描述如下：
**
中位数**是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如 `arr = [2,3,4]` 的中位数是 `3` 。
- 例如 `arr = [2,3]` 的中位数是 `(2 + 3) / 2 = 2.5` 。
实现 MedianFinder 类:
- `MedianFinder()` 初始化 `MedianFinder` 对象。
- `void addNum(int num)` 将数据流中的整数 `num` 添加到数据结构中。
- `double findMedian()` 返回到目前为止所有元素的中位数。与实际答案相差 `10-5` 以内的答案将被接受。
**示例 1：**
**输入**
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
**输出**
[null, null, null, 1.5, null, 2.0]
**解释**
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0
**提示:**
- `-105 <= num <= 105`
- 在调用 `findMedian` 之前，数据结构中至少有一个元素
- 最多 `5 * 104` 次调用 `addNum` 和 `findMedian`双堆法求中位数是常用操作，思路是这样的：构建一个大顶堆和一个小顶堆，大小是数据流大小的一半n/2（在偶数情况下），或者大顶堆大小是 (n/2) +1 （在数据流大小是奇数情况下）。
大顶堆数据用于维护较小的的半边数据，小顶堆用于维护较大的半边数据。
如果数据小于等于大顶堆堆顶元素则则将元素插入到大顶堆，否则将其插入到小顶堆。
如果插入之后大顶堆和小顶堆在偶数的时候不符合各占一半比例或者在奇数的时候大顶堆和小顶堆不是分别占n/2 +1和n/2，则需要将元素从较多的堆移动到较小的堆。
在数据是奇数的情况下，中位数就是大顶堆的堆顶元素，偶数情况下，就是大小顶堆的堆顶元素，两个元素的平均值。
public class LeetCode295 {
// 大顶堆存小元素
private Heap<Integer> bigHeap = new Heap<>(Heap.HeapType.BIG,32);
// 小顶堆存大元素
private Heap<Integer> minHeap = new Heap<>(Heap.HeapType.MIN,32);
public void addNum(Integer num) {
// 第一个元素
if(bigHeap.isEmpty() || num.compareTo(bigHeap.top()) <= 0){
// 小于大顶堆元素
ensureCapacity();
bigHeap.add(num);
}else {
ensureCapacity();
minHeap.add(num);
}
// 调整堆,因为没每次只有一个元素的差异，所以只需要调整一个元素
// 始终维护 bigHeap.size() ≥ minHeap.size() 且差值不超过1
if(bigHeap.size() > (minHeap.size() + 1) ){
// 如果大堆大与小堆两个
ensureCapacity();
minHeap.add(bigHeap.removeTop());
}else if(minHeap.size() > bigHeap.size()) {
// 如果小堆大于大堆
ensureCapacity();
bigHeap.add(minHeap.removeTop());
}
}
public double findMedian() {
if(bigHeap.isEmpty()){
return 0.0;
}
int allSize = bigHeap.size() + minHeap.size();
double result = 0.0;
if(allSize % 2 == 0){
// 偶数为堆顶元素之和的平均值
int sum = bigHeap.top() + minHeap.top();
result = (double) sum / 2.0;
}else {
result = bigHeap.top();
}
return result;
}
private void ensureCapacity(){
// 保证容量,双倍扩容
Heap<Integer> tempBigHeap = bigHeap;
Heap<Integer> tempMinHeap = minHeap;
// 更优解是复制底层数组，不过我的heap没有实现复制数组同时设置容量的功能
if(bigHeap.isFull()){
bigHeap = new Heap<>(Heap.HeapType.BIG,tempBigHeap.size() * 2);
while (!tempBigHeap.isEmpty()){
bigHeap.add(tempBigHeap.removeTop());
}
}
if(minHeap.isFull()){
minHeap = new Heap<>(Heap.HeapType.MIN,tempMinHeap.size() * 2);
while (!tempMinHeap.isEmpty()){
minHeap.add(tempMinHeap.removeTop());
}
}
}
}findMedian的时间复杂度是O(1)。
addNum的时间复杂度是O(log n)，集中在堆化操作。
评论已关闭