第十天：golang学习笔记之container

★container | heap堆操作, list双向链表,ring环形链表

现在网上的算法题，很少有可以用golang作答的，不过看看别人造的轮子还是挺有意思的
container本身并不是包，但目录下包括三个子包：heap，list，ring

heap

1. 包含一个Interface接口，接口定义了Push(x interface{})，Pop() interface{} ，并包含了sort.Interface接口。
2. 这里的堆是小顶堆
3. heap并没有可用的实现，但在test中找到一个：

// An IntHeap is a min-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    // Push and Pop use pointer receivers because they modify the slice's length,
    // not just its contents.
    *h = append(*h, x.(int))
}

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

4. 在进行heap.Pop，heap.Remove，heap.Push时，会自动fix为小顶堆

PS：所以堆拍啥的只要pop() pop() pop()就可以了

list ring

这俩一个尿性放一块看了
list是有头的所以有type List struct 和 type Element struct，Element是双向的并且有*List指针
ring是一个固定大小的环，仅由type Ring struct组成

有疑问加站长微信联系（非本文作者）