3.3 container — 容器数据类型：heap、list和ring

优质

小牛编辑

125浏览

2023-12-01

该包实现了三个复杂的数据结构：堆，链表，环。这个包就意味着你使用这三个数据结构的时候不需要再费心从头开始写算法了。

3.3.1 堆

这里的堆使用的数据结构是最小二叉树，即根节点比左边子树和右边子树的所有值都小。 go的堆包只是实现了一个接口，我们看下它的定义：

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

可以看出，这个堆结构继承自sort.Interface, 回顾下sort.Interface，它需要实现三个方法

Len() int
Less(i, j int) bool
Swap(i, j int)

加上堆接口定义的两个方法

Push(x interface{})
Pop() interface{}

就是说你定义了一个堆，就要实现五个方法，直接拿package doc中的example做例子：

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 interface{}) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

那么IntHeap就实现了这个堆结构，我们就可以使用堆的方法来对它进行操作：

h := &IntHeap{2, 1, 5}
heap.Init(h)
heap.Push(h, 3)
heap.Pop(h)

具体说下内部实现，是使用最小堆，索引排序从根节点开始，然后左子树，右子树的顺序方式。内部实现了down和up分别表示对堆中的某个元素向上保证最小堆和向上保证最小堆。

当往堆中插入一个元素的时候，这个元素插入到最右子树的最后一个节点中，然后调用up向上保证最小堆。

当要从堆中推出一个元素的时候，先吧这个元素和右子树最后一个节点兑换，然后弹出最后一个节点，然后对root调用down，向下保证最小堆。

3.3.2 链表

链表就是一个有prev和next指针的数组了。它维护两个type，(注意，这里不是interface)

type Element struct {
	next, prev *Element  // 上一个元素和下一个元素
	list *List  // 元素所在链表
	Value interface{}  // 元素
}

type List struct {
	root Element  // 链表的根元素
	len  int      // 链表的长度
}

基本使用是先创建list，然后往list中插入值，list就内部创建一个Element，并内部设置好Element的next,prev等。具体可以看下例子：

// This example demonstrates an integer heap built using the heap interface.
package main

import (
	"container/list"
	"fmt"
)

func main() {
    list := list.New()
    list.PushBack(1)
    list.PushBack(2)

    fmt.Printf("len: %v\n", list.Len());
    fmt.Printf("first: %#v\n", list.Front());
    fmt.Printf("second: %#v\n", list.Front().Next());
}

output:
len: 2
first: &list.Element{next:(*list.Element)(0x2081be1b0), prev:(*list.Element)(0x2081be150), list:(*list.List)(0x2081be150), Value:1}
second: &list.Element{next:(*list.Element)(0x2081be150), prev:(*list.Element)(0x2081be180), list:(*list.List)(0x2081be150), Value:2}

list对应的方法有：

type Element
    func (e *Element) Next() *Element
    func (e *Element) Prev() *Element
type List
    func New() *List
    func (l *List) Back() *Element   // 最后一个元素
    func (l *List) Front() *Element  // 第一个元素
    func (l *List) Init() *List  // 链表初始化
  func (l *List) InsertAfter(v interface{}, mark *Element) *Element // 在某个元素后插入
  func (l *List) InsertBefore(v interface{}, mark *Element) *Element  // 在某个元素前插入
    func (l *List) Len() int // 在链表长度
    func (l *List) MoveAfter(e, mark *Element)  // 把e元素移动到mark之后
    func (l *List) MoveBefore(e, mark *Element)  // 把e元素移动到mark之前
    func (l *List) MoveToBack(e *Element) // 把e元素移动到队列最后
    func (l *List) MoveToFront(e *Element) // 把e元素移动到队列最头部
    func (l *List) PushBack(v interface{}) *Element  // 在队列最后插入元素
    func (l *List) PushBackList(other *List)  // 在队列最后插入接上新队列
    func (l *List) PushFront(v interface{}) *Element  // 在队列头部插入元素
    func (l *List) PushFrontList(other *List) // 在队列头部插入接上新队列
    func (l *List) Remove(e *Element) interface{} // 删除某个元素

3.3.3 环

环的结构有点特殊，环的尾部就是头部，所以每个元素实际上就可以代表自身的这个环。它不需要像list一样保持list和element两个结构，只需要保持一个结构就行。

type Ring struct {
	next, prev *Ring
	Value      interface{}
}

我们初始化环的时候，需要定义好环的大小，然后对环的每个元素进行赋值。环还提供一个Do方法，能便利一遍环，对每个元素执行一个function。看下面的例子：

// This example demonstrates an integer heap built using the heap interface.
package main

import (
	"container/ring"
	"fmt"
)

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

    for i := 1; i <= 3; i++ {
        ring.Value = i
        ring = ring.Next()
    }

    // 计算1+2+3
    s := 0
    ring.Do(func(p interface{}){
        s += p.(int)
    })
    fmt.Println("sum is", s)
}

output:
sum is 6

ring提供的方法有

type Ring
    func New(n int) *Ring  // 初始化环
    func (r *Ring) Do(f func(interface{}))  // 循环环进行操作
    func (r *Ring) Len() int // 环长度
    func (r *Ring) Link(s *Ring) *Ring // 连接两个环
    func (r *Ring) Move(n int) *Ring // 指针从当前元素开始向后移动或者向前（n可以为负数）
    func (r *Ring) Next() *Ring // 当前元素的下个元素
    func (r *Ring) Prev() *Ring // 当前元素的上个元素
    func (r *Ring) Unlink(n int) *Ring // 从当前元素开始，删除n个元素