[仓颉Cangjie刷题模板] 优先队列(含小顶堆实现)
@[TOC]([仓颉Cangjie刷题模板] 优先队列(含小顶堆实现) )
一、 算法&数据结构
1. 描述
堆是一个可以维护实时最大/最小值的数据结构，相比treeset等常数优很多。
常用于维护一组数据的极值贪心问题。
2. 复杂度分析
- 初始化O(n)
- 查询O(1)
- 修改O(lgn)
3. 常见应用
- Dijkstra
- 丑数II
- 3D接雨水
4. 常用优化
- 本文模板实现的是小顶堆，要用大顶堆可以取反。
- 注意经常要用的元组，在仓颉里不能比大小，因此可以用数组代替，并实现扩展排序（但是很麻烦）；或者自己实现元组(pair等）
二、 模板代码
1. 丑数
例题: 264. 丑数 II
按照从小到大的顺序枚举每个丑数可以派生的丑数，那么第k次出堆的那个就是答案。
extend<T> Array<T> where T <: Less<T> {
operator func <(rhs: Array<T>): Bool {
for (i in 0..min(size, rhs.size)) {
if (this[i] < rhs[i]) {
return true
}
}
return this.size < rhs.size
}
// public func equals(other: Array<T>){
// return true
// }
}
class MinHeap<T> <: Collection<T> where T <: Less<T> {
public prop size: Int {
get() {h.size}
}
protected var h = ArrayList<T>()
public init() { }
public init(items: Collection<T>) {
h.appendAll(items)
for (i in (h.size/2)..=0:-1) {
_siftup(i)
}
}
public func isEmpty() {
return h.isEmpty()
}
public func iterator() {
throw Exception("No Iterator for MinHeap")
// return h.iterator()
}
public func heappush(v:T) {
h.append(v)
var i = h.size - 1
while (i > 0 && v < (h[(i-1) >> 1])) { // 比父节点小，则上移
h[i] = h[(i-1) >> 1]
i = (i-1) >> 1
}
h[i] = v
}
public func heappop() {
// let last = h.remove(h.size-1)
// if (h.size == 0) {
// return last
// }
// let ret = h[0]
// h[0] = last
// _siftup(0)
// return ret
let ret = h[0]
h[0] = h[h.size-1]
h.remove(h.size-1)
if (!h.isEmpty()) {
_siftup(0)
}
return ret
}
public func heapreplace(v:T) { // 替换并返回堆顶
let ret = h[0]
h[0] = v
_siftup(0)
return ret
}
public func heappushpop(v:T) { // 把v和堆顶保留更大的那个，pop返回更小的那个；常用语保留最大的k个值（小顶堆）
if (!h.isEmpty() && h[0] < v) {
let ret = h[0]
h[0] = v
return ret
}
return v
}
private func _siftup(i:Int64){
// 把i位置的大值下沉，小儿子提上来
var fa = i
let v = h[fa]
let n = h.size
while ( (fa << 1 | 1) < n) { // 有左儿子
var child = fa << 1 | 1
let right = child + 1
if (right < n && h[right] < h[child]) {
child = right
}
if (h[child] < v) {
h[fa] = h[child] // 小的儿子上移
fa = child // 迭代
} else {
break
}
}
if (fa != i) { // 有变化
h[fa] = v
}
}
}
extend<T> MinHeap<T> <: ToString where T <: ToString {
public func toString() {
return h.toString()
}
}
public class Solution {
public func nthUglyNumber(n: Int64): Int64 {
let h = MinHeap<Int64>([1])
let vis = HashSet<Int64>();
let q = [2,3,5]
for (_ in 0..n-1) {
let v = h.heappop()
for (i in q) {
let p = i*v
if (vis.contains(p)) {
continue
}
vis.put(p)
h.heappush(p)
}
}
return h.heappop()
}
}
2. Dijkstra模板体
例题: 743. 网络延迟时间
跑一遍Dij，距离最大的就是答案
import std.collection.*
import std.math.*
class MinHeap<T> <: Collection<T> where T <: MyLess<T> {
public prop size: Int {
get() {h.size}
}
protected var h = ArrayList<T>()
public init() { }
public init(items: Collection<T>) {
h.appendAll(items)
for (i in (h.size/2)..=0:-1) {
_siftup(i)
}
}
public func isEmpty() {
return h.isEmpty()
}
public func iterator() {
throw Exception("No Iterator for MinHeap")
// return h.iterator()
}
public func heappush(v:T) {
h.append(v)
var i = h.size - 1
while (i > 0 && v < (h[(i-1) >> 1])) { // 比父节点小，则上移
h[i] = h[(i-1) >> 1]
i = (i-1) >> 1
}
h[i] = v
}
public func heappop() {
// let last = h.remove(h.size-1)
// if (h.size == 0) {
// return last
// }
// let ret = h[0]
// h[0] = last
// _siftup(0)
// return ret
let ret = h[0]
h[0] = h[h.size-1]
h.remove(h.size-1)
if (!h.isEmpty()) {
_siftup(0)
}
return ret
}
public func heapreplace(v:T) { // 替换并返回堆顶
let ret = h[0]
h[0] = v
_siftup(0)
return ret
}
public func heappushpop(v:T) { // 把v和堆顶保留更大的那个，pop返回更小的那个；常用语保留最大的k个值（小顶堆）
if (!h.isEmpty() && h[0] < v) {
let ret = h[0]
h[0] = v
return ret
}
return v
}
private func _siftup(i:Int64){
// 把i位置的大值下沉，小儿子提上来
var fa = i
let v = h[fa]
let n = h.size
while ( (fa << 1 | 1) < n) { // 有左儿子
var child = fa << 1 | 1
let right = child + 1
if (right < n && h[right] < h[child]) {
child = right
}
if (h[child] < v) {
h[fa] = h[child] // 小的儿子上移
fa = child // 迭代
} else {
break
}
}
if (fa != i) { // 有变化
h[fa] = v
}
}
}
interface MyLess<T> {
operator func <(rhs: T): Bool
}
extend<T> Array<T> <: MyLess<Array<T>> where T <: Less<T> {
public operator func <(rhs: Array<T>): Bool {
for (i in 0..min(size, rhs.size)) {
if (this[i] < rhs[i]) {
return true
} else if (rhs[i] < this[i]) {
return false
}
}
return this.size < rhs.size
}
// public func equals(other: Array<T>){
// return true
// }
}
extend<T> MinHeap<T> <: ToString where T <: ToString {
public func toString() {
return h.toString()
}
}
public class Solution {
public func networkDelayTime(times: Array<Array<Int64>>, n: Int64, k: Int64): Int64 {
let g = Array(n, {_=>ArrayList<(Int64,Int64)>()})
for (e in times) {
let (u,v,w) = (e[0],e[1],e[2])
g[u-1].append((v-1,w))
}
let dis = Array(n, {_=>Int64.Max})
dis[k-1] = 0
let h = MinHeap([[0,k-1]])
while (!h.isEmpty()) {
let arr = h.heappop()
let (c, u) = (arr[0],arr[1])
if (c > dis[u]) {
continue
}
for (e in g[u]){
let (v, w) = (e[0],e[1])
if (c + w < dis[v]) {
dis[v] = c+w
h.heappush([c+w,v])
}
}
}
let ans = max(dis).getOrThrow()
return if (ans == Int64.Max){-1} else {ans}
}
}
三、其他
- 堆本质是一种贪心，因此在很多场景都有应用。比如区间离线问题
四、更多例题
五、参考链接
- [python刷题模板] 单调队列