Go语言开发（十四）、Go语言常用标准库四

Go语言开发（十四）、Go语言常用标准库四

一、heap

1、heap简介

heap仅仅提供了最小堆的操作，没有提供堆的数据结构，堆的数据结构必须由开发者自己实现。heap提供了一个heap.Interface接口来作为堆的操作和堆的数据结构（开发者自己实现）之间的桥梁，堆的数据结构必须满足此接口：

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

sort.Interface定义在sort.go中：

type Interface interface {
   // Len is the number of elements in the collection.
   Len() int
   // Less reports whether the element with
   // index i should sort before the element with index j.
   Less(i, j int) bool
   // Swap swaps the elements with indexes i and j.
   Swap(i, j int)
}

因此，开发者自己实现的堆必须要定义5个方法才能与heap协作使用。
func Fix(h Interface, i int)
当索引i的元素的值改变时，重建堆数据结构
func Init(h Interface)
初始化堆，在调用其它堆操作函数前应调用Init函数完成堆数据结构初始化
func Pop(h Interface) interface{}
弹出堆中的最小元素，返回弹出的元素
func Push(h Interface, x interface{})
添加元素到堆
func Remove(h Interface, i int) interface{}
移除索引为i的元素，返回被移除的元素

2、heap示例

IntHeap实现如下：

package IntHeap

type IntHeap []int

func (h IntHeap) Len() int {
   return len(h)
}
func (h IntHeap) Less(i, j int) bool {
   // 如果h[i]<h[j]生成的就是小根堆，如果h[i]>h[j]生成的就是大根堆
   return h[i] < h[j]
}
func (h IntHeap) Swap(i, j int) {
   h[i], h[j] = h[j], h[i]
}

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

func (h *IntHeap) Push(x interface{}) {
   *h = append(*h, x.(int))
}
IntHeap使用：
package main

import (
   "GoExample/Heap/IntHeap"
   "container/heap"
   "fmt"
)

func main() {
   h := &IntHeap.IntHeap{0, 8, 2, 3, 4, 1, 6, 7, 5}
   heap.Init(h)
   fmt.Println(*h)          //[0 3 1 5 4 2 6 7 8]
   fmt.Println(heap.Pop(h)) //0
   heap.Push(h, 6)
   fmt.Println(*h) // [1 3 2 5 4 8 6 7 6]
   for len(*h) > 0 {
      fmt.Printf("%d ", heap.Pop(h))
   }
   // 1 2 3 4 5 6 6 7 8
}

3、heap实现机制

heap内部使用最小(最大)堆，索引排序从根节点开始，然后左子树，右子树的顺序方式。内部实现的down和up分别表示对堆中的某个元素向下保证最小(最大)堆和向上保证最小(最大)堆。
当向堆中压入一个元素的时候，元素压入到最右子树的最后一个节点中，然后调用up向上保证最小(最大)堆。
当从堆中弹出一个元素的时候，先把元素和右子树最后一个节点交换，然后弹出最后一个节点，然后对root调用down，向下保证最小(最大)堆。
生成最小堆还是最大堆由Less方法决。

func (h IntHeap) Less(i, j int) bool {
   // 如果h[i]<h[j]生成的就是小根堆，如果h[i]>h[j]生成的就是大根堆
   return h[i] < h[j]
}

二、list

1、list简介

list实现了一个双向链表，链表及链表节点的数据结构如下：

type Element struct {
   next, prev *Element
   list *List
   Value interface{}
}
type List struct {
   root Element // sentinel list element, only &root, root.prev, and root.next are used
   len  int     // current list length excluding (this) sentinel element
}

Element定义了两个Element类型的指针next，prev以及List类型的指针list，Value用来存储值，List定义了一个Element作为链表的Root，len作为链表的长度。
list提供的方法如下：

func (e *Element) Next() *Element
func (e *Element) Prev() *Element
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{}                      // 删除某个元素

2、list使用示例

package main

import (
   "container/list"
   "fmt"
)

func main() {
   l := list.New()
   l.PushBack(123)
   l.PushBack("456")
   l.PushBack(false)
   fmt.Println(l.Len())                       // 3
   fmt.Println(l.Front().Value)               // 123
   fmt.Println(l.Front().Next().Value)        // 456
   fmt.Println(l.Front().Next().Next().Value) // false
   fmt.Println(l.Back().Value)                // false
   fmt.Println(l.Back().Prev().Value)         // 456
}

三、ring

1、ring简介

ring包提供了环形链表的操作，ring导出Ring类型，数据结构如下：

// Ring表示环形链表中的元素。
type Ring struct {
   Value interface{} // Value类型为interface{}，因此可以接受任意类型
}

// 创建一个长度为n的环形链表
func New(n int) *Ring

// 针对环形链表中的每一个元素x进行f(x)操作
func (r *Ring) Do(f func(interface{}))

// 获取环形链表长度
func (r *Ring) Len() int

// 如果r和s在同一环形链表中，则删除r和s之间的元素，
// 被删除的元素组成一个新的环形链表，返回值为该环形链表的指针（即删除前，r->Next()表示的元素）
// 如果r和s不在同一个环形链表中，则将s插入到r后面，返回值为
// 插入s后，s最后一个元素的下一个元素（即插入前，r->Next()表示的元素）
func (r *Ring) Link(s *Ring) *Ring

// 移动 n % r.Len() 个位置，n正负均可
func (r *Ring) Move(n int) *Ring

// 返回下一个元素
func (r *Ring) Next() *Ring

// 返回前一个元素
func (r *Ring) Prev() *Ring

// 删除r后面的 n % r.Len() 个元素
func (r *Ring) Unlink(n int) *Ring

2、ring使用示例

Josephus问题如下：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
Josephus问题使用ring的解决方案如下：

package main

import (
   "container/ring"
   "fmt"
)

const (
   playerCount = 41 // 玩家人数
   startPos    = 1  // 开始报数位置
   deadline    = 3  // 第n个人自杀
   aliveCount  = 2  // 幸存人数
)

type Player struct {
   position int  // 位置
   alive    bool // 是否存活
}

var players = ring.New(playerCount)

func Play(playerList *ring.Ring) {
   // 设置所有玩家初始值
   for i := 1; i <= playerCount; i++ {
      playerList.Value = &Player{i, true}
      playerList = playerList.Next()
   }

   // 如果开始报数的位置不为1，则设置开始位置
   if startPos > 1 {
      playerList = playerList.Move(startPos - 1)
   }

   counter := 1   // 报数从1开始
   deadCount := 0 // 死亡人数，初始值为0

   for deadCount < playerCount-aliveCount {
      playerList = playerList.Next() // 跳到下一个人
      // 如果是活着的人，则报数
      if playerList.Value.(*Player).alive {
         counter++
      }
      // 如果报数为deadline，则此人淘汰出局
      if counter == deadline {
         playerList.Value.(*Player).alive = false
         fmt.Printf("Player %d died!\n", playerList.Value.(*Player).position)
         deadCount++
         counter = 0 // 报数置成0
      }
   }
}

func main() {
   Play(players)
   players.Move(startPos)
   for i := 1; i < playerCount; i++ {
      if players.Value.(*Player).alive {
         fmt.Println("alive: ", players.Value.(*Player).position)
      }
      players = players.Next()
   }
}

四、sort

1、sort简介

sort包中实现了四种基本排序算法：插入排序、归并排序、堆排序和快速排序，但只被用于sort包内部使用。在对数据集合排序时不必考虑应当选择哪一种排序方法，只要实现了sort.Interface定义的三个方法：获取数据集合长度的Len()方法、比较两个元素大小的Less()方法和交换两个元素位置的Swap()方法，就可以顺利对数据集合进行排序。sort包会根据实际数据自动选择高效的排序算法。为了方便对常用数据类型的操作，sort包提供了对[]int切片、[]float64切片和[]string切片完整支持，主要包括：
（1）对基本数据类型切片的排序支持。
（2）基本数据元素查找。
（3）判断基本数据类型切片是否已经排好序。
（4）对排好序的数据集合逆序。
对数据集合（包括自定义数据类型的集合）排序需要实现sort.Interface接口的三个方法：

type Interface interface {
   // 返回要排序的数据长度
   Len() int
   //比较下标为i和j对应的数据大小，可自己控制升序和降序
   Less(i, j int) bool
   // 交换下标为i，j对应的数据
   Swap(i, j int)
}

任何实现了sort.Interface 的类型（一般为集合），均可使用sort包中的方法进行排序，sort.Interface接口的方法要求集合内列出元素的索引为整数。

2、sort使用示例

package main

import (
   "fmt"
   "sort"
)

type Person struct {
   Name string
   Age  int
}

type PersonArray []Person

func (a PersonArray) Len() int {
   return len(a)
}
func (a PersonArray) Swap(i, j int) {
   a[i], a[j] = a[j], a[i]
}
func (a PersonArray) Less(i, j int) bool {

   return a[i].Age < a[j].Age
}

func main() {
   peoples := []Person{
      {"Bob", 31},
      {"John", 42},
      {"Michael", 17},
      {"Bauer", 26},
   }

   fmt.Println(peoples)
   sort.Sort(PersonArray(peoples))
   fmt.Println(peoples)
}

// output:
// [{Bob 31} {John 42} {Michael 17} {Bauer 26}]
// [{Michael 17} {Bauer 26} {Bob 31} {John 42}]