主体思路
听老师的讲解就好
注意细节
需要额外的数组来存“次数”和“位置”信息,不然在堆里找不到位置
基础代码
package main
import (
"fmt"
"os"
"bufio"
)
var (
in = bufio.NewReader(os.Stdin)
out = bufio.NewWriter(os.Stdout)
h, ph, hp [100010]int
// h[k] 存储堆中的值
// hp[k] 存储堆中下标是 k 的点是第几个插入的
// ph[k] 存储第k个插入的点在堆中的位置
size int
)
func heapSwap(a, b int) {
ph[hp[a]], ph[hp[b]] = ph[hp[b]], ph[hp[a]]
hp[a], hp[b] = hp[b], hp[a]
h[a], h[b] = h[b], h[a]
}
func down(u int) {
t := u
if u * 2 <= size && h[u * 2] < h[t] { t = u * 2 }
if u * 2 + 1 <= size && h[u * 2 + 1] < h[t] { t = u * 2 + 1 }
if u != t {
heapSwap(u, t)
down(t)
}
}
func up(u int) {
for u >> 1 > 0 && h[u] < h[u >> 1] {
heapSwap(u, u >> 1)
u >>= 1
}
}
func main() {
n, m := 0, 0
fmt.Fscan(in, &n)
for ; n > 0; n-- {
var op string
var k, x int
fmt.Fscan(in, &op)
switch op {
case "I":
fmt.Fscan(in, &x)
size++; m++
ph[m] = size; hp[size] = m; h[size] = x
// h[size] 存储堆中的值 就是堆尾添加
// hp[size] 存储堆中下标是 size 的点是第几个插入的, 就是 m
// ph[m] 存储第 m 个插入的点在堆中的位置, 就是 size
up(size)
case "PM":
fmt.Fprint(out, h[1], "\n")
case "DM":
heapSwap(1, size)
size--
down(1)
case "D":
fmt.Fscan(in, &k) // 原本输入是“第 k 次插入”
k = ph[k] // 通过ph数组查询出第 k 次插入的值的位置,并将其更新为 k ,简单来说,到这里的 k 已经从【次数】转变成【位置】
heapSwap(k, size)
size--; up(k); down(k)
case "C":
fmt.Fscan(in, &k, &x)
k = ph[k]; h[k] = x // 通过ph数组, k 从【次数】转变成【位置】
up(k); down(k)
}
}
out.Flush()
}