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)
}
}
```
有疑问加站长微信联系（非本文作者）
