Question

数据结构有很多种，标准库只提供了常用的链表和最小堆。如对性能或存储量有较高要求，建议使用第三方专业版本。

双向链表

平平无奇的双向链表。

type Element struct {
	Value any
}

环状链表

由多个 Ring 元素构成一个环状链表（circular list）。持有任何一个都可以访问全部。

type Ring struct {
    Value any
}

package main

import (
	"container/ring"
	"fmt"
)

func main() {
	r := ring.New(3)

	for i := 0; i < r.Len(); i++ {
		r.Value = i + 100
		r = r.Next()
	}

	// 合并
	r2 := ring.New(2)
	r2.Value = 4
	r2.Next().Value = 5
	r.Link(r2)

	// 遍历
	r.Do(func(v any) {
		fmt.Println(v.(int))
	})
}

/*

100
4
5
101
102

*/

func main() {
	r := ring.New(5)

	for i := 0; i < r.Len(); i++ {
		r.Value = i + 100
		r = r.Next()
	}

	// 分离
	r2 := r.Unlink(3)

	r.Do(func(v any) {
		fmt.Println(v.(int))
	})

	r2.Do(func(v any) {
		fmt.Println("  ", v.(int))
	})
}

/*

100
104
   101
   102
   103
   
*/

最小堆

最小堆结构，常用来实现优先级队列。须实现 heap.Interface 接口。

// sort
type Interface interface {
	Len() int
	Less(i, j int) bool
	Swap(i, j int)
}

// heap
type Interface interface {
	sort.Interface
    
	Push(x any) // add x as element Len()
	Pop() any   // remove and return element Len() - 1.
}

实现这些方法后，通过 heap 里的函数进行操作。注意，有序 是针对 heap 而言，而非底层结构。

• Init ：将目标初始化为有序堆。
• Push ：压入数据，并保持有序。
• Pop ：弹出 “最小” 数据。
• Fix ：修改元素值后修复，使堆保持有序状态。
• Remove ：删除元素，并维持堆有序。

package main

import (
	"container/heap"
	"fmt"
)

// ---------------------------------------

type Message struct {
	text     string
	priority int
}

type Queue []Message

func (q Queue) Len() int {
	return len(q)
}

func (q Queue) Less(i, j int) bool {
	return q[i].priority < q[j].priority
}

func (q Queue) Swap(i, j int) {
	q[i], q[j] = q[j], q[i]
}

func (q *Queue) Push(x any) {
	*q = append(*q, x.(Message))
}

func (q *Queue) Pop() any {
	n := len(*q)
	x := (*q)[n-1]
	*q = (*q)[:n-1]
	return x
}

// ---------------------------------------

func main() {
	var q Queue = []Message{
		{"a3", 3},
		{"a1", 1},
		{"a4", 4},
		{"a2", 2},
		{"a0", 0},
	}

	heap.Init(&q)
	heap.Push(&q, Message{"a5", 1})

	q[0].priority += 10
	heap.Fix(&q, 0)

	fmt.Println(q)

	for q.Len() > 0 {
		fmt.Println(heap.Pop(&q).(Message))
	}
}

/*

[{a1 1} {a2 2} {a5 1} {a0 10} {a3 3} {a4 4}]

{a1 1}
{a5 1}
{a2 2}
{a3 3}
{a4 4}
{a0 10}

*/

要实现最大堆也很容易，将 Less 方法改一下即可。

func (q Queue) Less(i, j int) bool {
	// return q[i].priority < q[j].priority
	return q[i].priority > q[j].priority
}