# 3.3 container — 容器数据类型：heap、list和ring #
该包实现了三个复杂的数据结构：堆，链表，环。
这个包就意味着你使用这三个数据结构的时候不需要再费心从头开始写算法了。
## 3.3.1 堆 ##
这里的堆使用的数据结构是最小二叉树，即根节点比左边子树和右边子树的所有值都小。
go的堆包只是实现了一个接口，我们看下它的定义：
```golang
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做例子：
```golang
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就实现了这个堆结构，我们就可以使用堆的方法来对它进行操作：
```golang
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)
```golang
type Element struct {
next, prev *Element // 上一个元素和下一个元素
list *List // 元素所在链表
Value interface{} // 元素
}
type List struct {
root Element // 链表的根元素
len int // 链表的长度
}
```
基本使用是先创建list，然后往list中插入值，list就内部创建一个Element，并内部设置好Element的next,prev等。具体可以看下例子：
```golang
// 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两个结构，只需要保持一个结构就行。
```golang
type Ring struct {
next, prev *Ring
Value interface{}
}
```
我们初始化环的时候，需要定义好环的大小，然后对环的每个元素进行赋值。环还提供一个Do方法，能便利一遍环，对每个元素执行一个function。
看下面的例子：
```golang
// 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个元素
```
# 导航 #
- [第三章 数据结构与算法](/chapter03/03.0.md)
- 上一节：index/suffixarray — 后缀数组实现子字符串查询
- 下一节：container总结
- 简介
- 第一章 输入输出 (Input/Output)
- 1.1 io — 基本的 IO 接口
- 1.2 ioutil — 方便的 IO 操作函数集
- 1.3 fmt — 格式化 IO
- 1.4 bufio — 缓存 IO
- 第二章 文本
- 2.1 strings — 字符串操作
- 2.2 bytes — byte slice 便利操作
- 2.3 strconv — 字符串和基本数据类型之间转换
- 2.4 regexp — 正则表达式
- 2.5 unicode — Unicode 码点、UTF-8/16 编码
- 第三章 数据结构与算法
- 3.1 sort — 排序算法
- 3.2 index/suffixarray — 后缀数组实现子字符串查询
- 3.3 container — 容器数据类型：heap、list 和 ring
- 第四章 日期与时间
- 4.1 主要类型概述
- 4.2 时区
- 4.3 Time类型详解
- 4.4 定时器
- 第六章 文件系统
- 6.1 os — 平台无关的操作系统功能实现
- 6.2 path/filepath — 操作路径
- 第七章 数据持久存储与交换
- 7.1 database/sql — SQL/SQL-Like 数据库操作接口
- 第八章 数据压缩与归档
- 8.1 flate * DEFLATE 压缩算法
- 第九章 测试
- 9.1 testing * 单元测试
- 9.2 testing * 基准测试
- 9.3 testing * 子测试
- 9.4 testing * 运行并验证示例
- 9.5 testing * 其他功能
- 9.6 httptest * HTTP 测试辅助工具
- 9.7 总结
- 第十章 进程、线程与 goroutine
- 10.1 创建进程
- 10.2 进程属性和控制
- 10.3 线程
- 10.4 进程间通信
- 第十三章 应用构建 与 debug
- 13.1 flag * 命令行参数解析
- 13.2 log * 日志记录
- 13.3 expvar * 公共变量的标准化接口
- 13.4 runtime/debug * 运行时的调试工具