Golang的container库有哪些数据结构 介绍heap与list的实现

package main

import (
    "container/list"
    "fmt"
)

func main() {
    myList := list.New() // 创建一个新的链表

    myList.PushBack("Hello") // 在尾部添加元素
    myList.PushFront("World") // 在头部添加元素
    element := myList.PushBack("Go") // 添加并获取元素指针

    myList.InsertBefore("Awesome", element) // 在"Go"之前插入"Awesome"

    fmt.Println("List elements:")
    for e := myList.Front(); e != nil; e = e.Next() {
        fmt.Printf("%v ", e.Value)
    }
    fmt.Println() // Output: World Hello Awesome Go

    myList.Remove(element) // 移除"Go"

    fmt.Println("List after removing 'Go':")
    for e := myList.Front(); e != nil; e = e.Next() {
        fmt.Printf("%v ", e.Value)
    }
    fmt.Println() // Output: World Hello Awesome
}

package main

import (
    "container/heap"
    "fmt"
)

// IntHeap 是一个实现了 heap.Interface 的 int 切片
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] }

// Push 方法将元素 x 添加到 IntHeap 中
func (h *IntHeap) Push(x any) {
    *h = append(*h, x.(int))
}

// Pop 方法从 IntHeap 中移除并返回最小元素
func (h *IntHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func main() {
    h := &IntHeap{2, 1, 5}
    heap.Init(h) // 初始化堆，使其满足堆属性

    heap.Push(h, 3) // 推入新元素
    fmt.Printf("minimum: %d\n", (*h)[0]) // Output: minimum: 1

    for h.Len() > 0 {
        fmt.Printf("%d ", heap.Pop(h)) // 弹出最小元素
    }
    fmt.Println() // Output: 1 2 3 5
}

package main

import (
    "container/heap"
    "fmt"
)

// Item 是优先队列中的一个元素
type Item struct {
    value    string // 元素的值
    priority int    // 元素的优先级
    index    int    // 元素在堆中的索引，用于更新优先级
}

// PriorityQueue 实现了 heap.Interface 接口
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

// Less 方法定义了优先级规则：优先级数值越小，优先级越高
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i // 更新索引
    pq[j].index = j // 更新索引
}

func (pq *PriorityQueue) Push(x any) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() any {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil // 避免内存泄漏
    item.index = -1 // 表示元素已从堆中移除
    *pq = old[0 : n-1]
    return item
}

// Update 修改指定元素的优先级
func (pq *PriorityQueue) Update(item *Item, value string, priority int) {
    item.value = value
    item.priority = priority
    heap.Fix(pq, item.index) // 重新调整堆
}

func main() {
    items := map[string]int{
        "taskA": 3,
        "taskB": 2,
        "taskC": 1,
    }

    pq := make(PriorityQueue, len(items))
    i := 0
    for value, priority := range items {
        pq[i] = &Item{
            value:    value,
            priority: priority,
            index:    i,
        }
        i++
    }
    heap.Init(&pq) // 初始化堆

    // 添加一个新任务
    itemD := &Item{value: "taskD", priority: 4}
    heap.Push(&pq, itemD)

    // 更新一个任务的优先级
    pq.Update(itemD, itemD.value, 0) // taskD 优先级变为最高

    fmt.Println("Processing tasks by priority:")
    for pq.Len() > 0 {
        item := heap.Pop(&pq).(*Item)
        fmt.Printf("Task: %s, Priority: %d\n", item.value, item.priority)
    }
    // Output will be:
    // Task: taskD, Priority: 0
    // Task: taskC, Priority: 1
    // Task: taskB, Priority: 2
    // Task: taskA, Priority: 3
}

package main

import (
    "container/ring"
    "fmt"
)

func main() {
    // 创建一个包含5个元素的环
    r := ring.New(5)

    // 填充环
    for i := 0; i < r.Len(); i++ {
        r.Value = i + 1
        r = r.Next() // 移动到下一个元素
    }

    fmt.Println("Ring elements:")
    r.Do(func(p any) { // 遍历环
        fmt.Printf("%v ", p)
    })
    fmt.Println() // Output: 1 2 3 4 5

    // 移动环的指针
    r = r.Move(2) // 向前移动2步，现在r指向元素3

    fmt.Println("Ring elements after moving 2 steps (starting from current r):")
    r.Do(func(p any) {
        fmt.Printf("%v ", p)
    })
    fmt.Println() // Output: 3 4 5 1 2

    // 添加一个新元素，会覆盖当前r指向的元素
    r.Value = 99
    fmt.Println("Ring elements after changing current element to 99:")
    r.Do(func(p any) {
        fmt.Printf("%v ", p)
    })
    fmt.Println() // Output: 99 4 5 1 2
}