Go语言中利用最小优先队列高效处理条件式递增序列

package main

import (
    "fmt"
)

// MinPQ 表示一个最小优先队列，通过二叉堆实现。
// 它存储原始数据的索引，以保持原始切片不变。
type MinPQ struct {
    values  []float64 // 原始输入列表的引用
    indices []int     // 存储原始切片中元素的索引，构成二叉堆
    size    int       // 当前堆中元素的数量
}

// NewMinPQ 创建一个新的最小优先队列。
// 它接收一个浮点数切片作为输入，并构建一个基于索引的最小堆。
func NewMinPQ(set []float64) *MinPQ {
    m := &MinPQ{
        values:  set,
        indices: make([]int, 1, len(set)+1), // 索引从1开始，所以需要额外空间
        size:    0,
    }

    // 遍历原始切片，将每个元素的索引添加到堆中并进行上浮操作
    for i := range set {
        m.indices = append(m.indices, i) // 添加索引
        m.size++                         // 堆大小增加
        m.swim(m.size)                   // 上浮操作，维护堆的性质
    }
    return m
}

// Empty 返回堆是否为空。
func (m *MinPQ) Empty() bool {
    return m.size == 0
}

// Dequeue 移除并返回堆中最小的元素。
// 如果堆为空，则返回0。
func (m *MinPQ) Dequeue() float64 {
    if m.Empty() {
        return 0
    }

    // 最小元素是堆顶元素（索引为1）在原始切片中的值
    minIndexInOriginalSlice := m.indices[1]

    // 交换堆顶元素和最后一个元素
    m.swap(1, m.size)
    m.size-- // 堆大小减一
    m.sink(1) // 下沉操作，恢复堆的性质

    // 移除最后一个元素（现在是原堆顶元素）
    m.indices = m.indices[:m.size+1]

    return m.values[minIndexInOriginalSlice]
}

// greater 比较两个索引对应的原始值大小。
// 如果 x 索引对应的值大于 y 索引对应的值，则返回 true。
func (m *MinPQ) greater(x, y int) bool {
    return m.values[m.indices[x]] > m.values[m.indices[y]]
}

// swap 交换堆中两个位置的索引。
func (m *MinPQ) swap(i, j int) {
    m.indices[i], m.indices[j] = m.indices[j], m.indices[i]
}

// sink 将位于 k 位置的元素下沉，以维护堆的性质。
func (m *MinPQ) sink(k int) {
    for 2*k <= m.size { // 只要有左子节点
        j := 2 * k // 左子节点索引

        // 如果存在右子节点且右子节点小于左子节点，则选择右子节点
        if j < m.size && m.greater(j, j+1) {
            j++
        }

        // 如果父节点小于或等于子节点，则无需下沉
        if !m.greater(k, j) {
            break
        }

        m.swap(k, j) // 交换父子节点
        k = j        // 继续下沉
    }
}

// swim 将位于 k 位置的元素上浮，以维护堆的性质。
func (m *MinPQ) swim(k int) {
    // 只要不是根节点且父节点大于当前节点
    for k > 1 && m.greater(k/2, k) {
        m.swap(k, k/2) // 交换父子节点
        k /= 2         // 继续上浮
    }
}

// doSmallest 从优先队列中取出最小元素并进行处理。
// 如果处理结果进入 default 分支，则递归地处理下一个最小元素。
func doSmallest(queue *MinPQ) {
    if queue.Empty() {
        return
    }

    v := queue.Dequeue() // 取出当前最小元素

    switch v {
    case 1:
        fmt.Printf("处理值: %.0f (匹配到 case 1)\n", v)
    case 2:
        fmt.Printf("处理值: %.0f (匹配到 case 2)\n", v)
    case 3:
        fmt.Printf("处理值: %.0f (匹配到 case 3)\n", v)
    case 4:
        fmt.Printf("处理值: %.0f (匹配到 case 4)\n", v)
    case 5:
        fmt.Printf("处理值: %.0f (匹配到 case 5)\n", v)
    default:
        // 未匹配到特定 case，递归处理下一个最小元素
        fmt.Printf("值 %.0f 未匹配，处理下一个最小元素...\n", v)
        doSmallest(queue) // 递归调用
    }
}

func main() {
    slice := []float64{2, 1, 13, 4, 22, 0, 5, 7, 3}
    fmt.Printf("原始切片顺序: %v\n", slice)

    // 创建最小优先队列
    queue := NewMinPQ(slice)

    // 循环处理队列中的所有元素
    for !queue.Empty() {
        doSmallest(queue)
    }

    fmt.Printf("处理后原始切片顺序: %v\n", slice) // 验证原始切片未被修改
}

原始切片顺序: [2 1 13 4 22 0 5 7 3]
值 0 未匹配，处理下一个最小元素...
处理值: 1 (匹配到 case 1)
处理值: 2 (匹配到 case 2)
处理值: 3 (匹配到 case 3)
处理值: 4 (匹配到 case 4)
处理值: 5 (匹配到 case 5)
值 7 未匹配，处理下一个最小元素...
值 13 未匹配，处理下一个最小元素...
值 22 未匹配，处理下一个最小元素...
处理后原始切片顺序: [2 1 13 4 22 0 5 7 3]