知识卡片

普通读书笔记卡 · 3634.a.7.a

离线最小值按插入段分组

理解等级:中级

把操作序列按 EXTRACT-MIN 分成插入段 I₁…Iₘ₊₁。

按键从小到大处理时,将当前键分配给它插入段之后最早仍有效的取最小值位置,再把该段与下一有效段合并。

原文给出过程,正确性和并查集实现仍留作练习。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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