原来的末端节点需要与新位置上的父节点做比较,如果小于要做 up(看上面的方法),如果大于父节点,则再和子节点做比较,即 down 操作,直到该节点下降到小于最小子节点为止。
与子节点进行比较交换的 down 操作的流程用代码表示为:
func(h Heap)down(i int) { for { l := 2*i + 1// 左孩子 r := 2*i +2// 右孩子 if l >= len(h) { break// i 已经是叶子节点,退出操作。 } j := l if r < len(h) && h.less(r, l) { j = r // 右孩子为最小子节点 } // i 与最小子节点进行比较 if h.less(i, j) { break// 如果父节点比子节点小,则不交换 } h.swap(i, j) // 交换父子节点 i = j //继续向下比较 } }
实现了核心的up 和down 操作后,堆的Remove操作便很简单,代码如下:
// 删除堆中位置为i的元素 // 返回被删元素的值 func(h *Heap)Remove(i int)(int, bool) { if i < 0 || i > len(*h)-1 { return0, false } n := len(*h) - 1 h.swap(i, n) // 用最后的元素值替换被删除元素 // 删除最后的元素 x := (*h)[n] *h = (*h)[0:n] // 如果当前元素大于父节点,向下筛选 if i == 0 || (*h)[i] > (*h)[(i-1)/2] { h.down(i) } else { // 当前元素小于父节点,向上筛选 h.up(i) } return x, true }
type Interface interface { sort.Interface Push(x any) // add x as element Len() Pop() any // remove and return element Len() - 1. }
它匿名嵌套的 sort.Interface 的定义如下:
type Interface interface { // Len is the number of elements in the collection. Len() int // Less reports whether the element with // index i should sort before the element with index j. Less(i, j int) bool // Swap swaps the elements with indexes i and j. Swap(i, j int) }
也就是说,我们要使用go标准库给我们提供的heap,那么必须自己实现上面两个接口定义的方法,这些方法的实现方式就是我们上面演示的建堆、插入、删除这些操作,这里就不再继续演示 Go 这个 heap 库的使用啦。