Go 算法与容器实践：遍历、排序、递推与堆

本轮只做理论正文与源码静态复核；下列命令、示例和测试均未执行。已有输出按代码推演或历史记录理解，不作为本轮运行证据。

练习范围与前置

先完成 Go 的函数、指针与结构体、切片、接口和测试。算法复杂度、递归和数据结构分别从算法专题学习；本页关注用 Go 表达与验证它们。各代码块在独立模块中运行，不要拼成一个包含多个 main 的程序。

二叉树与遍历顺序

图中边表示父子关系，括号内是前序访问序号。到节点就输出，然后完整走完左子树，再进入右子树，所以 2 必须在 3、4 之后输出。若把输出移到两次递归之间，顺序会改成中序。

查看图表代码

先明确树形，再讨论遍历。下例是一棵普通二叉树，不是二叉搜索树；节点值大小不决定左右位置。前序访问的顺序是根、左、右。

package main

import "fmt"

type Node struct {
    Value int
    Left, Right *Node
}

func Preorder(node *Node, visit func(int)) {
    if node == nil { return }
    visit(node.Value)
    Preorder(node.Left, visit)
    Preorder(node.Right, visit)
}

func main() {
    root := &Node{Value: 0,
        Left: &Node{Value: 1, Left: &Node{Value: 3}, Right: &Node{Value: 4}},
        Right: &Node{Value: 2},
    }
    var values []int
    Preorder(root, func(value int) { values = append(values, value) })
    fmt.Println(values)
}

输出 [0 1 3 4 2]。遍历访问每个节点一次，时间为 O(n)；递归栈随树高增长，退化成长链时可能很深。层序遍历需要队列；按层填充节点与按大小插入搜索树是两种不同操作。

排序与边界输入

业务代码先使用标准库，手写快速排序、冒泡排序时另行说明分区不变量、终止条件与复杂度。快速排序每次只交换一对元素却不循环完成分区，不能保证两边已经满足分区条件；空切片也不能直接读取中间元素。算法推导见排序专题。

package main

import (
    "fmt"
    "sort"
)

func main() {
    values := []int{3, -1, 3, 0, 2}
    sort.Ints(values)
    fmt.Println(values)
    sort.Sort(sort.Reverse(sort.IntSlice(values)))
    fmt.Println(values)
}

输出 [-1 0 2 3 3] 和 [3 3 2 0 -1]。这两次排序都修改原切片；需要保留原值时，先复制元素。不要把某台机器的 slice/list 插入或遍历耗时当作容器选择规则，比较时必须固定操作位置、规模与测量方式。

递推、递归与数值边界

下面用较小的 n=4 展示重复子问题：朴素递归的 F(2) 会在两个分支出现。缓存可把它合并为一个状态；只求最终一项时，滚动保存相邻两项进一步消除整张表。算法减少重复运算，但不会扩大 uint64 的可表示范围。

查看图表代码

斐波那契先定义 F(0)=0、F(1)=1，后续为前两项之和，开头是 0, 1, 1, 2, 3, 5, 8。直接递归会重复计算；只求一项时，迭代可用 O(n) 时间、O(1) 额外空间。

package main

import (
    "fmt"
    "errors"
)

func Fibonacci(n int) (uint64, error) {
    if n < 0 || n > 93 { return 0, errors.New("n must be between 0 and 93") }
    if n == 0 { return 0, nil }
    var previous, current uint64 = 0, 1
    for i := 1; i < n; i++ { previous, current = current, previous+current }
    return current, nil
}

func main() {
    for _, n := range []int{0, 1, 2, 10, 93, 94} {
        value, err := Fibonacci(n)
        fmt.Println(n, value, err)
    }
}

前五个结果为 0、1、1、55、12200160415121876738，错误为 nil；94 超出 uint64 可表示的斐波那契范围，返回错误。负数也应拒绝。

倒推题先写清“当前剩余”如何得到“前一步总数”：

• 猴子每天吃一半再多一个，第 10 天剩 1 个。从 1 开始反推 9 次 before = 2 * (remaining + 1)，第一天为 1534；递归参数应说明指剩余天数还是总天数。
• 卖鱼前四次分别卖当时总数的 1/2、1/3、1/4、1/5，并各多卖相应的 1/2、1/3、1/4、1/5 条，最后卖余下 11 条。按除数 5、4、3、2 倒推 before = (d * remaining + 1) / (d - 1)，每步先检查整除，依次得到 14、19、29、59。原有鱼 59 条。

标准库容器与最小堆

接口的 Pop 删除切片尾部，是供堆算法调用的底层操作。包级 heap.Pop 先把根与尾交换，再恢复剩余堆序，最后才调用接口 Pop 返回移到尾部的旧根，因此输出最小值。直接调用 h.Pop 只会取尾部，不能保证最小。

查看图表代码

需求	选择与约束
连续列表、栈和遍历	通常先考虑切片
按键查找	map；稳定顺序另行维护
反复取最小或最大元素	container/heap，比较由 Less 决定
持有节点并频繁移动或删除	container/list 双向链表，零值可用，PushBack 是尾插
环形节点结构	container/ring；先确认是否真的需要节点环

package main

import (
    "container/heap"
    "fmt"
)

type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any {
    old := *h
    n := len(old)
    value := old[n-1]
    *h = old[:n-1]
    return value
}

func main() {
    h := &IntHeap{3, 1, 2}
    heap.Init(h)
    heap.Push(h, 0)
    for h.Len() > 0 { fmt.Print(heap.Pop(h), " ") }
    fmt.Println()
}

使用 Go 1.18 起的 any（interface{} 的别名），预期输出 0 1 2 3。包级 heap.Push/Pop 负责维护堆序；接口方法 Push 只追加到末尾、Pop 只删除末尾，不应直接用它们代替包级调用。更新优先级时还需维护节点索引并调用 heap.Fix；包含指针的元素被删除后需考虑清空尾部引用。API 依据：container/heap。

练习与验收

为遍历测试空树、单节点和偏斜树；排序测试 nil、空、重复、负数、已排序与逆序输入。递推验证 0、1、2、93 的结果及 -1、94 的错误；倒推题再正向验算每次卖出或吃掉的数量。堆测试空堆不弹出、重复值和改写 Less 后的最大堆顺序；使用测试课的表格测试组织断言。

书面自检答案

提示：先按输入不变量手算，不把上文输出称为本轮实测。空树不调用visit；单节点仅输出一次；原地排序会改原切片，保留输入需先复制。Fibonacci(-1)、Fibonacci(94)返回错误，Fibonacci(93)=12200160415121876738；无符号结果不代表可无限增长。空堆不能调用heap.Pop。

综合练习参考答案

将Less反向后预期最大值先出，重复值应按重复次数保留；堆接口Pop删除末尾不等于包级heap.Pop直接返回末尾。倒推猴子1534后依次正向减半再减1，9次后为1。卖鱼59依次余29、19、14、11，再卖完，契合题意。代码块各自保存为独立main.go；Go标准库之外无依赖，未执行。