知识卡片

普通读书笔记卡 · 3634.a.5.b

加权合并总把短链接长链

理解等级:中级

加权合并为链表维护长度,总把较短链表接到较长链表后。单次合并仍可能线性,但减少同一元素反复更换所属集合指针的次数;成本保证针对整段操作序列。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第19章《不相交集合的数据结构》(OEBPS/chapter019.xhtml,文本字符[10000,15000))。 - 结论依据:原文定义按长度加权的合并规则,并限定单次与序列成本。 - 原始内容:Suppose instead that each list also includes the length of the list (which can be maintained straightforwardly with constant overhead) and that the U NION procedure always appends the shorter list onto the longer, breaking ties arbitrarily.