Hello go (XIV). Go language common standard library IV

One 、heap

1、heap brief introduction

heap Only minimal heap operations are provided , No data structure for heap provided , The data structure of the heap must be implemented by the developer .heap Provides a heap.Interface Interface as the operation of the heap and the data structure of the heap （ Developers themselves ） The bridge between , The data structure of the heap must meet this interface ：

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

sort.Interface It's defined in sort.go in ：

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

therefore , The heap implemented by the developer must be defined 5 There are only three ways to match heap Collaborative use of .

func Fix(h Interface, i int)

When indexing i When the value of the element changes , Rebuild the heap data structure

func Init(h Interface)

Initializing the heap , Call... Before calling other heap operation functions Init Function to initialize the heap data structure

func Pop(h Interface) interface{}

Eject the smallest element in the heap , Return the pop-up element

func Push(h Interface, x interface{})

Add elements to the heap

func Remove(h Interface, i int) interface{}

Remove index to i The elements of , Return the removed element

2、heap Example

IntHeap The implementation is as follows ：

package IntHeap

type IntHeap []int

func (h IntHeap) Len() int {
   return len(h)
}
func (h IntHeap) Less(i, j int) bool {
   //  If h[i]<h[j] What is generated is the small root heap , If h[i]>h[j] What is generated is the big root heap 
   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 Use ：

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 Implementation mechanism

heap Minimum for internal use ( Maximum ) Pile up , Index sorting starts at the root node , Then the left subtree , The order of right subtree . Internally realized down and up Respectively, it means to guarantee the minimum downward for an element in the heap ( Maximum ) Heap and up guarantee minimum ( Maximum ) Pile up .

When pressing an element into the heap , The element is pushed into the last node of the rightmost subtree , And then call up Keep the minimum upward ( Maximum ) Pile up .

When an element is ejected from the heap , First, exchange the element with the last node of the right subtree , And then the last node pops up , Then on root call down, Keep the minimum down ( Maximum ) Pile up .

Whether to generate the minimum heap or the maximum heap is determined by Less Method decision .

func (h IntHeap) Less(i, j int) bool {
   //  If h[i]<h[j] What is generated is the small root heap , If h[i]>h[j] What is generated is the big root heap 
   return h[i] < h[j]
}

Two 、list

1、list brief introduction

list Implemented a two-way linked list , The data structure of the linked list and its nodes is as follows ：

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 Two are defined Element Pointer to type next,prev as well as List Pointer to type list,Value Used to store values ,List Defined a Element As a linked list Root,len As the length of the linked list .

list The method provided is as follows ：

func (e *Element) Next() *Element
func (e *Element) Prev() *Element
func New() *List
func (l *List) Back() *Element                                     //  Return to the last element 
func (l *List) Front() *Element                                    //  Returns the first element 
func (l *List) Init() *List                                        //  Initialization of linked list 
func (l *List) InsertAfter(v interface{}, mark *Element) *Element  //  Insert... Before an element 
func (l *List) InsertBefore(v interface{}, mark *Element) *Element //  Insert... After an element 
func (l *List) Len() int                                           //  Return the length of the list 
func (l *List) MoveAfter(e, mark *Element)                         //  hold e Element moved to mark after 
func (l *List) MoveBefore(e, mark *Element)                        //  hold e Element moved to mark Before 
func (l *List) MoveToBack(e *Element)                              //  hold e The element moves to the end of the queue 
func (l *List) MoveToFront(e *Element)                             //  hold e The element moves to the top of the queue 
func (l *List) PushBack(v interface{}) *Element                    //  Insert the element at the end of the queue 
func (l *List) PushBackList(other *List)                           //  Insert a new queue at the end of the queue 
func (l *List) PushFront(v interface{}) *Element                   //  Insert elements at the head of the queue 
func (l *List) PushFrontList(other *List)                          //  Insert a new queue at the head of the queue 
func (l *List) Remove(e *Element) interface{}                      //  Delete an element 

2、list Examples of use

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
}

3、 ... and 、ring

1、ring brief introduction

ring Package provides the operation of circular linked list ,ring export Ring type , The data structure is as follows ：

// Ring Represents the elements in the circular linked list .
type Ring struct {
   Value interface{} // Value The type is interface{}, Therefore, any type of 
}

//  Create a length of n Ring list of 
func New(n int) *Ring

//  For each element in the circular linked list x Conduct f(x) operation 
func (r *Ring) Do(f func(interface{}))

//  Get the length of the circular linked list 
func (r *Ring) Len() int

//  If r and s In the same circular linked list , Delete r and s Between the elements ,
//  The deleted elements form a new circular linked list , The return value is the pointer of the circular linked list （ That is, before deleting ,r->Next() Represents the element ）
//  If r and s Not in the same circular linked list , Will s Insert into r Back , The return value is 
//  Insert s after ,s The next element of the last element （ Before insertion ,r->Next() Represents the element ）
func (r *Ring) Link(s *Ring) *Ring

//  Move  n % r.Len()  A place ,n Both positive and negative 
func (r *Ring) Move(n int) *Ring

//  Returns the next element 
func (r *Ring) Next() *Ring

//  Return to the previous element 
func (r *Ring) Prev() *Ring

//  Delete r hinder  n % r.Len()  Elements 
func (r *Ring) Unlink(n int) *Ring

2、ring Examples of use

Josephus Questions as follows ： After the Romans took jotapat ,39 Jews and Josephus And his friends in a cave ,39 A Jew decided to die rather than be caught by the enemy , So I decided to commit suicide ,41 Individuals in a circle , From the first 1 Individual starts counting , Count to 3 You have to kill yourself , And then count again by the next , Until everyone killed himself . However Josephus And his friends didn't want to comply . Start with one person , Skip over k-2 personal （ Because the first one has been crossed ）, And kill No k personal . next , Over again k-1 personal , And kill No k personal . The process goes all the way around the circle , Until there's only one left , This man can live on . The problem is , Given and , Where to stand at first to avoid being executed ？Josephus Ask his friend to pretend to obey first , He arranged his friend and himself in the 16 And 31 A place , So I escaped the game of death .

Josephus Problem using ring The solution is as follows ：

package main

import (
   "container/ring"
   "fmt"
)

const (
   playerCount = 41 //  Number of players 
   startPos    = 1  //  Start counting position 
   deadline    = 3  //  The first n Personal suicide 
   aliveCount  = 2  //  The number of survivors 
)

type Player struct {
   position int  //  Location 
   alive    bool //  Survival 
}

var players = ring.New(playerCount)

func Play(playerList *ring.Ring) {
   //  Set all players' initial values 
   for i := 1; i <= playerCount; i++ {
      playerList.Value = &Player{i, true}
      playerList = playerList.Next()
   }

   //  If the starting position is not 1, Then set the start position 
   if startPos > 1 {
      playerList = playerList.Move(startPos - 1)
   }

   counter := 1   //  Count off from 1 Start 
   deadCount := 0 //  The number of deaths , The initial value is 0

   for deadCount < playerCount-aliveCount {
      playerList = playerList.Next() //  Jump to the next person 
      //  If you are a living person , Then report 
      if playerList.Value.(*Player).alive {
         counter++
      }
      //  If the number is deadline, Then this person is eliminated 
      if counter == deadline {
         playerList.Value.(*Player).alive = false
         fmt.Printf("Player %d died!\n", playerList.Value.(*Player).position)
         deadCount++
         counter = 0 //  Alarm setting 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()
   }
}

Four 、sort

1、sort brief introduction

sort Four basic sorting algorithms are implemented in the package ： Insertion sort 、 Merge sort 、 Heap sort and quick sort , But only for sort Package internal use . It is not necessary to consider which sort method should be selected when sorting data sets , As long as it's done sort.Interface Three methods of definition ： Gets the length of the data set Len() Method 、 Compare the size of two elements Less() Method and exchanging the positions of two elements Swap() Method , You can sort the data set smoothly .sort The package will automatically select an efficient sorting algorithm based on the actual data . In order to facilitate the operation of common data types ,sort The package provides []int section 、[]float64 Slicing and []string Slice complete support , It mainly includes ：

（1） Sorting support for basic data type slices .

（2） Basic data element lookup .

（3） Determine whether the basic data type slice has been sorted .

（4） Reverse the ordered data set .

For data sets （ Includes a collection of custom data types ） Sorting needs to be done sort.Interface Three methods of interface ：

type Interface interface {
   //  Returns the length of the data to sort 
   Len() int
   // The comparison subscript is i and j Corresponding data size , You can control the ascending and descending order by yourself 
   Less(i, j int) bool
   //  The exchange subscript is i,j Corresponding data 
   Swap(i, j int)
}

Any implementation sort.Interface The type of （ Generally set ）, All can use sort The methods in the package ,sort.Interface The method of the interface requires the index of the listed elements in the collection to be an integer .

2、sort Examples of use

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