Go标准库heap源码中的一个细节问题

wallace_lai · · 2287 次点击 · 开始浏览    置顶
这是一个创建于 的主题,其中的信息可能已经有所发展或是发生改变。

Go标准库提供了二叉堆的接口实现,源码在heap.go中。以下是其中几个核心函数。up和down分别表示自顶向下和自底向上调整二叉堆的过程。 (1)对于down方法来说,如果发生了交换,即将节点i与其左右子树中最小的j发生了交换,则满足`i > i0`返true,若没有发生交换则返回false (2)对于up方法来说,则是不断重复地将当前节点i与其父结点j比较,若节点i的值小于节点j的值则交换(默认为小顶堆),直到遇到了根节点为止 ```go func up(h Interface, j int) { for { i := (j - 1) / 2 // parent if i == j || !h.Less(j, i) { break } h.Swap(i, j) j = i } } func down(h Interface, i0, n int) bool { i := i0 for { j1 := 2*i + 1 if j1 >= n || j1 < 0 { // j1 < 0 after int overflow break } j := j1 // left child if j2 := j1 + 1; j2 < n && h.Less(j2, j1) { j = j2 // = 2*i + 2 // right child } if !h.Less(j, i) { break } h.Swap(i, j) i = j } return i > i0 } ``` 对于Remove方法,若待删除的节点i刚好是最末尾的元素则啥也不做直接调用用户提供的Pop方法将末尾元素移除即可。否则需要将节点i与末尾节点n交换,随后从i节点处自顶向下地调整堆结构使其符合二叉堆的性质。 那么问题来了,**为什么在down方法返false,即没有发生交换的情况下,需要从节点i开始调用up进行自底向上地调整二叉堆**?**被交换到i处的末尾元素n与原先的i节点是子节点的关系,肯定不会小于节点i的值,那必定也是不比节点i的父节点的值小,即小顶堆的性质是满足的,那为何还要调用up方法呢**? ```go // Remove removes and returns the element at index i from the heap. // The complexity is O(log n) where n = h.Len(). func Remove(h Interface, i int) any { n := h.Len() - 1 if n != i { h.Swap(i, n) if !down(h, i, n) { up(h, i) } } return h.Pop() } ``` Fix也是一样的情况,为何需要调用up? ```go // Fix re-establishes the heap ordering after the element at index i has changed its value. // Changing the value of the element at index i and then calling Fix is equivalent to, // but less expensive than, calling Remove(h, i) followed by a Push of the new value. // The complexity is O(log n) where n = h.Len(). func Fix(h Interface, i int) { if !down(h, i, h.Len()) { up(h, i) } } ```

有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

2287 次点击  
加入收藏 微博
3 回复  |  直到 2023-05-31 23:00:00
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传