知识卡片
离线最小值按插入段分组
把操作序列按 EXTRACT-MIN 分成插入段 I₁…Iₘ₊₁。
按键从小到大处理时,将当前键分配给它插入段之后最早仍有效的取最小值位置,再把该段与下一有效段合并。
原文给出过程,正确性和并查集实现仍留作练习。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第19章 不相交集合的数据结构 · 查看原书依据
OFFLINE-MINIMUM(m, n) 1 for i = 1 to n 2 determine j such that i ∈ Kj 3 if j ≠ m + 1 4 extracted[j] = i 5 let l be the smallest value greater than j for which set Kl exists 6 Kl = Kj ∪ Kl, destroying Kj 7 return extracted
参考来源
- 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[40000,45000))。
- 结论依据:题目给出分段表示和OFFLINE-MINIMUM过程,并把正确性与实现证明另列为任务。
- 原始内容:O FFLINE -M INIMUM ( m , n ) 1 for i = 1 to n 2 determine j such that i ∈ K j 3 if j ≠ m + 1 4 extracted [ j ] = i 5 let l be the smallest value greater than j for which set K l exists 6 K l = K j ∪ K l , destroying K j 7 return extracted