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}]