知识卡片
堆序约束不等于整体排序
最小堆只要求父节点在比较关系下不大于子节点,因此根给出最小元素;兄弟和不同子树之间没有全序保证。底层切片看起来局部无序并不意味着堆坏了。要连续得到有序结果,需按堆操作反复取最小值,而不是直接顺序读取切片。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 05.9.1 使用 container/heap · 查看原书依据
中的 2.1 1.2 3.1 这三个数的顺序看上去有些不对,这是因为堆不是按照线性逻辑进行排序的。请记住,堆是一个树状结构,而不是像数组或切片这样的线性结构。
参考来源
- 位置:《精通 Go(Mastering Go 中文版)》05.9.1 使用 container/heap,spine099(book-sources;extracted/精通 Go(Mastering Go 中文版)/_epub-src/05.9.1.html)。
- 结论依据:原文最终输出2.1、1.2、3.1次序与堆的树形约束对应。
- 原始内容:中的 2.1 1.2 3.1 这三个数的顺序看上去有些不对,这是因为堆不是按照线性逻辑进行排序的。请记住,堆是一个树状结构,而不是像数组或切片这样的线性结构。