此包定义了三个数据结构以供直接使用：heap（堆）、list（双向链表）、ring（环形链表）。

用途：heap可用于快速排序，list可用于类似队列和栈这种，ring用于定长的循环队列，例如轮播

heap

首先堆是什么？堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

1、堆中某个节点的值总是不大于或不小于其父节点的值；2、堆总是一棵完全二叉树（下图）。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等

heap包通过接口描述了5个函数，只要自己实现了这5个函数，就是定义了一个堆

//heap.Interface
type Interface interface {
	sort.Interface
	Push(x interface{}) // 尾端加入
	Pop() interface{}   // 从尾端取出
}

//sort.Interface
type Interface interface {
	Len() int
	Less(i, j int) bool //决定从大到小排，还是从小到大排
	Swap(i, j int)
}

 例子

import "container/heap"
import "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] }  //表示从小到大排序，如果return h[i] > h[j]则相反
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
//push和pop使用指针接收器，这样可以同时修改slice的长度和内容
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
}

func main() {
	h := &IntHeap{2, 1, 5}
	heap.Init(h) //将h排序，此时h是&[1 2 5]
	heap.Push(h, 3) //尾端插入3，此时h是&[1 2 5 3]
	//heap.Remove(h,2) //去除指定索引的值
	for h.Len() > 0 {
		fmt.Printf("%d ", heap.Pop(h)) //按照预定义的从小到大或者从大到小的顺序取出值
	}
	// Output:
	// 1 2 3 5
}

list

例子

import "container/list"
import "fmt"

func main(){
	l := list.New()  //新建一个空链表 *List
	e4 := l.PushBack(4) //链表最后插入，返回插入的元素的地址 *Element
	e1 := l.PushFront(1)  //链表前面插入，返回插入的元素的地址 *Element
	l.InsertBefore(3, e4)
	l.InsertAfter(2, e1)

	for e := l.Front(); e != nil; e = e.Next() { //通过l.Front()取到链表第一个元素，l.Back()取最后一个元素
		fmt.Println(e.Value)
	}
}
//output:
//1
//2
//3
//4
其他
e4.Prev() e4.Next() //返回前一个元素、后一个元素的地址
l.Init() //清空链表
l.Front() l.Back()//返回第一个元素、最后一个元素的地址
l.Len() //链表的长度
l.MoveAfter(e1,e4) l.MoveBefore(e4,e1)  //将第一个元素移到第二个元素的后面、前面
l.Remove(e1) //移除指定元素，传入nil会报错
l.MoveToFront(e4) l.MoveToBack(e1) //将元素移到头部和尾部
l.PushFrontList(l) l.PushBackList(l) //将传入的链表拼接到l的前面、后面

其中数据结构

// List 表示双向链表
type List struct {
	root Element // sentinel list element, only &root, root.prev, and root.next are used
	len  int     // 当前列表长度
}

type Element struct {
	next, prev *Element //指向前一个、后一个元素
	list *List // 指向该元素所属的链表
	Value interface{} // 该元素储存的值
}

ring

ring的结构很简单：

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

例子

import "container/ring"
import "fmt"

func main() {
	r := ring.New(5) //首先需要定义ring的长度
	n := r.Len()
	for i := 0; i < n; i++ {
		r.Value = i
		r = r.Next()  //此时又指向0
	}
	for j := 0; j < n; j++ {
		fmt.Println(r.Value)
		r = r.Next()
	}
	// Output:
	// 0
	// 1
	// 2
	// 3
	// 4
}

ring的连接:link

import "container/ring"
import "fmt"

func main() {
	r := ring.New(3)
	s := ring.New(3)
	lr := r.Len()
	ls := s.Len()

	for i := 0; i < lr; i++ {
		r.Value = i
		r = r.Next()  //指向0
	}

	for j := 0; j < ls; j++ {
		s.Value = j+3
		s = s.Next()  //指向3
	}

	rs := r.Link(s) //在r指向的值后面接s，即0后面接s

	rs.Do(func(p interface{}) { //此时rs指向原来的r指向值的下一个，即1
		fmt.Println(p.(int))
	})
	// Output:
	//1
	//2
	//0
	//3
	//4
	//5
}

unlink

func main() {
	r := ring.New(6)
	n := r.Len()

	for i := 0; i < n; i++ {
		r.Value = i
		r = r.Next() //0到5，此时指向0
	}

	r.Unlink(3)	//从r.Next()开始，从r移除3个元素，返回这三个元素组成的ring

	r.Do(func(p interface{}) {
		fmt.Println(p.(int))
	})

	// Output:
	// 0
	// 4
	// 5
}