heap僅僅提供了最小堆的操作，沒有提供堆的數(shù)據(jù)結(jié)構(gòu)，堆的數(shù)據(jù)結(jié)構(gòu)必須由開發(fā)者自己實現(xiàn)。heap提供了一個heap.Interface接口來作為堆的操作和堆的數(shù)據(jù)結(jié)構(gòu)（開發(fā)者自己實現(xiàn)）之間的橋梁，堆的數(shù)據(jù)結(jié)構(gòu)必須滿足此接口：
重慶分公司
重慶分公司
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)
}因此，開發(fā)者自己實現(xiàn)的堆必須要定義5個方法才能與heap協(xié)作使用。func Fix(h Interface, i int)
當(dāng)索引i的元素的值改變時，重建堆數(shù)據(jù)結(jié)構(gòu)func Init(h Interface)
初始化堆，在調(diào)用其它堆操作函數(shù)前應(yīng)調(diào)用Init函數(shù)完成堆數(shù)據(jù)結(jié)構(gòu)初始化func Pop(h Interface) interface{}
彈出堆中的最小元素，返回彈出的元素func Push(h Interface, x interface{})
添加元素到堆func Remove(h Interface, i int) interface{}
移除索引為i的元素，返回被移除的元素
IntHeap實現(xiàn)如下：
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]生成的就是大根堆
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
} heap內(nèi)部使用最小(大)堆，索引排序從根節(jié)點開始，然后左子樹，右子樹的順序方式。內(nèi)部實現(xiàn)的down和up分別表示對堆中的某個元素向下保證最小(大)堆和向上保證最小(大)堆。
當(dāng)向堆中壓入一個元素的時候，元素壓入到最右子樹的最后一個節(jié)點中，然后調(diào)用up向上保證最小(大)堆。
當(dāng)從堆中彈出一個元素的時候，先把元素和右子樹最后一個節(jié)點交換，然后彈出最后一個節(jié)點，然后對root調(diào)用down，向下保證最小(大)堆。
生成最小堆還是大堆由Less方法決。
func (h IntHeap) Less(i, j int) bool {
// 如果h[i]h[j]生成的就是大根堆
return h[i] < h[j]
} list實現(xiàn)了一個雙向鏈表，鏈表及鏈表節(jié)點的數(shù)據(jù)結(jié)構(gòu)如下：
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{} // 刪除某個元素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包提供了環(huán)形鏈表的操作，ring導(dǎo)出Ring類型，數(shù)據(jù)結(jié)構(gòu)如下：
// Ring表示環(huán)形鏈表中的元素。
type Ring struct {
Value interface{} // Value類型為interface{}，因此可以接受任意類型
}
// 創(chuàng)建一個長度為n的環(huán)形鏈表
func New(n int) *Ring
// 針對環(huán)形鏈表中的每一個元素x進(jìn)行f(x)操作
func (r *Ring) Do(f func(interface{}))
// 獲取環(huán)形鏈表長度
func (r *Ring) Len() int
// 如果r和s在同一環(huán)形鏈表中，則刪除r和s之間的元素，
// 被刪除的元素組成一個新的環(huán)形鏈表，返回值為該環(huán)形鏈表的指針（即刪除前，r->Next()表示的元素）
// 如果r和s不在同一個環(huán)形鏈表中，則將s插入到r后面，返回值為
// 插入s后，s最后一個元素的下一個元素（即插入前，r->Next()表示的元素）
func (r *Ring) Link(s *Ring) *Ring
// 移動 n % r.Len() 個位置，n正負(fù)均可
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) *RingJosephus問題如下：在羅馬人占領(lǐng)喬塔帕特后，39個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數(shù)，每報數(shù)到第3人該人就必須自殺，然后再由下一個重新報數(shù)，直到所有人都自殺身亡為止。然而Josephus和他的朋友并不想遵從。首先從一個人開始，越過k-2個人（因為第一個人已經(jīng)被越過），并殺掉第k個人。接著，再越過k-1個人，并殺掉第k個人。這個過程沿著圓圈一直進(jìn)行，直到最終只剩下一個人留下，這個人就可以繼續(xù)活著。問題是，給定了和，一開始要站在什么地方才能避免被處決？Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。
Josephus問題使用ring的解決方案如下：
package main
import (
"container/ring"
"fmt"
)
const (
playerCount = 41 // 玩家人數(shù)
startPos = 1 // 開始報數(shù)位置
deadline = 3 // 第n個人自殺
aliveCount = 2 // 幸存人數(shù)
)
type Player struct {
position int // 位置
alive bool // 是否存活
}
var players = ring.New(playerCount)
func Play(playerList *ring.Ring) {
// 設(shè)置所有玩家初始值
for i := 1; i <= playerCount; i++ {
playerList.Value = &Player{i, true}
playerList = playerList.Next()
}
// 如果開始報數(shù)的位置不為1，則設(shè)置開始位置
if startPos > 1 {
playerList = playerList.Move(startPos - 1)
}
counter := 1 // 報數(shù)從1開始
deadCount := 0 // 死亡人數(shù)，初始值為0
for deadCount < playerCount-aliveCount {
playerList = playerList.Next() // 跳到下一個人
// 如果是活著的人，則報數(shù)
if playerList.Value.(*Player).alive {
counter++
}
// 如果報數(shù)為deadline，則此人淘汰出局
if counter == deadline {
playerList.Value.(*Player).alive = false
fmt.Printf("Player %d died!\n", playerList.Value.(*Player).position)
deadCount++
counter = 0 // 報數(shù)置成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包中實現(xiàn)了四種基本排序算法：插入排序、歸并排序、堆排序和快速排序，但只被用于sort包內(nèi)部使用。在對數(shù)據(jù)集合排序時不必考慮應(yīng)當(dāng)選擇哪一種排序方法，只要實現(xiàn)了sort.Interface定義的三個方法：獲取數(shù)據(jù)集合長度的Len()方法、比較兩個元素大小的Less()方法和交換兩個元素位置的Swap()方法，就可以順利對數(shù)據(jù)集合進(jìn)行排序。sort包會根據(jù)實際數(shù)據(jù)自動選擇高效的排序算法。為了方便對常用數(shù)據(jù)類型的操作，sort包提供了對[]int切片、[]float64切片和[]string切片完整支持，主要包括：
（1）對基本數(shù)據(jù)類型切片的排序支持。
（2）基本數(shù)據(jù)元素查找。
（3）判斷基本數(shù)據(jù)類型切片是否已經(jīng)排好序。
（4）對排好序的數(shù)據(jù)集合逆序。
對數(shù)據(jù)集合（包括自定義數(shù)據(jù)類型的集合）排序需要實現(xiàn)sort.Interface接口的三個方法：
type Interface interface {
// 返回要排序的數(shù)據(jù)長度
Len() int
//比較下標(biāo)為i和j對應(yīng)的數(shù)據(jù)大小，可自己控制升序和降序
Less(i, j int) bool
// 交換下標(biāo)為i，j對應(yīng)的數(shù)據(jù)
Swap(i, j int)
}任何實現(xiàn)了sort.Interface 的類型（一般為集合），均可使用sort包中的方法進(jìn)行排序，sort.Interface接口的方法要求集合內(nèi)列出元素的索引為整數(shù)。
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}]另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
