共计 4103 个字符，预计需要花费 11 分钟才能阅读完成。
1 前言
在之前的文章里，我分享了 Js 版的堆实现和 C 语言版的堆实现, 了解的话，堆的实现其实并不难，以大顶堆为例，简略演绎就是插入时候，比节点小，就一直向下沉，让更大的上浮，直到最大的上浮到根节点。
1. 数据与构造与算法: 堆 C 语言形容
2. 数据结构与算法: 堆 优先队列 JavaScript 语言形容
优先队列基于堆实现，顾名思义是一个有优先级的队列，最高优先级的最先出列，低优先级最初出列（如果是最小堆则刚好相同）。明天咱们就用堆和优先队列高效解决一些问题，别离是经典的 TopK 问题 - 堆解法，以及 3D 接雨水 - 优先队列解法。
2 TopK问题 - 堆解法
题目：215. 数组中的第 K 个最大元素
2.1 思路
在之前的文章里，我分享了基于 Partition 和ThreePartition算法的原地排序，来高效求解 TopK 问题，原地排序，没有应用额定的空间，空间复杂度很低，然而工夫复杂度稳定比拟大，如果随机取的基准值很现实，那么效率超高，但如果数组里值散布很发散，随机取的基准值也很不现实，那么这种极其状况下，那么效率就不是很高, 尽管《算法导论》证实了 Partition 算法是近似线性，但其线性常数项相对比 1 大多了；
而堆解法呢，就是稳固的工夫空间复杂度，建堆的最差复杂度是确定的，遍历一遍的复杂度只有O(N), 能够确定在kLog(k) + O(N)。
2.2 C语言形容
先建设一个容量为 k 的最小堆，后续的元素，只有比堆顶大的，才入堆，否则间接略过，最初堆顶元素就是第 K 大元素。
typedef struct MinHeap {
int *data; // 数据域
int size; // 长度
int max;// 最大长度
} MinHeap;
void insert(struct MinHeap *p, int item){if (p->size == p->max)
{printf("******:\n");
return;
}
int i = ++p->size;
for (; p->data[i/2] > item; i/=2)
{if (i <= 1)
{break;}
p->data[i] = p->data[i/2];
}
p->data[i] = item;
}
void delete(struct MinHeap *p){p->data[1] = p->data[p->size--];
int i = 1;
int tmp;
while(2*i <= p->size){
// 如果有右节点
if (2*i + 1 <= p->size)
{if (p->data[2*i + 1] < p->data[i] || p->data[2*i] < p->data[i])
{if (p->data[2*i + 1] < p->data[2*i])
{tmp = p->data[i];
p->data[i] = p->data[2*i + 1];
p->data[2*i + 1] = tmp;
i = 2*i + 1;
}else{tmp = p->data[i];
p->data[i] = p->data[2*i];
p->data[2*i] = tmp;
i = 2*i;
}
}else{return;}
}else{
// 只有左节点
if (p->data[2*i] < p->data[i])
{tmp = p->data[i];
p->data[i] = p->data[2*i];
p->data[2*i] = tmp;
i = 2*i;
}else{return;}
}
}
}
int findKthLargest(int* nums, int numsSize, int k){
struct MinHeap *heap;
heap=(struct MinHeap *)malloc(sizeof(struct MinHeap));
if (heap == NULL)
{printf("malloc error \n");
return 0;
}
heap->size = 0;
heap->max = k + 1;
heap->data = (int*)malloc(sizeof(int)*heap->max);
if(heap->data == NULL)
{printf("malloc error \n");
return 0;
}
heap->data[0] = 9999;
for (int i = 0; i < numsSize; ++i)
{if(i < k){insert(heap, nums[i]);
}else{if(nums[i] > heap->data[1]){delete(heap);
insert(heap, nums[i]);
}
}
}
return heap->data[1];
}
3 3D接雨水 - 优先队列解法
题目：407. 接雨水 II
3.1 思路
之前在枯燥栈进阶里分享过 2D 接雨水，那个尽管是 hard 但比较简单;3D接雨水思考的比 2D 多了些，不能只思考两边的高度，而是要思考周围，只有周围都比本人高，能力接得住雨水；思路呢其实就是把最外围的记录下来，扔到优先队列里 (小堆)，而后一直让堆顶出队，去更新堆顶元素的周围，而后把周围的入堆，如果周围的元素有比堆顶还低的，显然能够接到雨水。PS: 感觉我解说的必定没有题解清晰，倡议看题解。
## 3.2 Js语言形容
var Heap = function () {this.data = []
this.insert = (obj) => {
let i = this.data.length
for (; i > 0 && this.data[Math.floor((i - 1) / 2)].val >= obj.val; i = Math.floor((i - 1) / 2)) {if (i < 1) {break}
this.data[i] = this.data[Math.floor((i - 1) / 2)]
}
this.data[i] = obj
}
this.pop = () => {if (this.data.length == 0) {return null}
if (this.data.length == 1) {return this.data.pop()
}
let top = this.data[0]
this.data[0] = this.data.pop()
let i = 0
while (2 * i + 1 < this.data.length) {if (2 * i + 2 < this.data.length) {if (this.data[2 * i + 2].val < this.data[i].val || this.data[2 * i + 1].val < this.data[i].val) {if (this.data[2 * i + 2].val < this.data[2 * i + 1].val) {this.swap(i, 2 * i + 2)
i = 2 * i + 2
} else {this.swap(i, 2 * i + 1)
i = 2 * i + 1
}
} else {break}
} else {if (this.data[2 * i + 1].val < this.data[i].val) {this.swap(i, 2 * i + 1)
i = 2 * i + 1
} else {break}
}
}
return top
}
this.swap = (i, j) => {let tmp = this.data[j]
this.data[j] = this.data[i]
this.data[i] = tmp
}
};
3.3 Rust语言形容
思路都是一样的，仅仅语言不同
use std::cmp::Ordering;
use std::collections::BinaryHeap;
#[derive(Copy, Clone, Eq, PartialEq)]
struct Item {
val: i32,
i: usize,
j: usize,
}
impl Ord for Item {fn cmp(&self, other: &Self) -> Ordering {other.val.cmp(&self.val)
}
}
impl PartialOrd for Item {fn partial_cmp(&self, other: &Self) -> Option<Ordering> {Some(self.cmp(other))
}
}
impl Solution {pub fn trap_rain_water(height_map: Vec<Vec<i32>>) -> i32 {let h = height_map.len();
let w = height_map[0].len();
if h <= 2 || w <= 2 {return 0;}
let mut water = vec![vec![-1; w]; h];
let mut pq: BinaryHeap<Item> = BinaryHeap::new();
let mut i = 0;
while i < h {water[i][0] = height_map[i][0];
water[i][w - 1] = height_map[i][w - 1];
pq.push(Item {val: height_map[i][0],
i: i,
j: 0,
});
pq.push(Item {val: height_map[i][w - 1],
i: i,
j: w - 1,
});
i += 1;
}
i = 1;
while i < w - 1 {water[0][i] = height_map[0][i];
water[h - 1][i] = height_map[h - 1][i];
pq.push(Item {val: height_map[0][i],
i: 0,
j: i,
});
pq.push(Item {val: height_map[h - 1][i],
i: h - 1,
j: i
});
i += 1;
}
let dirs :[i32;5] = [-1, 0, 1, 0, -1];
let mut res = 0;
let mut k;
while pq.len() > 0 {if let Some(Item { val, i, j}) = pq.pop() {
k = 0;
while k < 4 {let nx = (i as i32 + dirs[k]) as usize;
let ny = (j as i32 + dirs[k+1]) as usize;
if 0 < nx && nx < h as usize && 0 < ny && ny < w && water[nx][ny] == -1 {if height_map[nx][ny] < val {res += val - height_map[nx][ny];
}
water[nx][ny] = val;
pq.push(Item {val: val.max(height_map[nx][ny]),
i: nx,
j: ny
});
}
k += 1;
}
}
}
return res;
}
}
正文完
