内容简介:heap仅仅提供了最小堆的操作,没有提供堆的数据结构,堆的数据结构必须由开发者自己实现。heap提供了一个heap.Interface接口来作为堆的操作和堆的数据结构(开发者自己实现)之间的桥梁,堆的数据结构必须满足此接口:sort.Interface定义在sort.go中:IntHeap实现如下:
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}]
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- Go语言开发(十一)、Go语言常用标准库一
- 区块链技术语言(三十):Go语言常用工具包
- Go语言开发(十三)、Go语言常用标准库三
- Go语言开发(十五)、Go语言常用标准库五
- Go语言开发(十六)、Go语言常用标准库六
- ASP程序中常用的脚本语言
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。