container/heap

#Interface

关于堆的介绍参看Heap。

在Go中实现的是一个最小堆，即每个节点的值总是以该节点为根节点的子树的最小值。同时应当注意到，对于任意一个节点，假设其下表为i，则其父节点下标为(i - 1) / 2，其左子节点下标为2 * i + 1，其右子节点下标为2 * i + 2。

在heap包中，定义了一个heap.Interface接口，只要实现该接口的数据结构，都可以作为一个堆来使用。

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

#down 和 up

heap操作中最重要的两个方法是down和up。

down让一个节点下沉：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func down(h Interface, i0, n int) bool {
    i := i0
    for {
        // j1为左子节点下标
        j1 := 2*i + 1
        if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
            break
        }
        j := j1 // left child
        // j2为右子节点下标，j为最小的子节点的下标
        if j2 := j1 + 1; j2 < n && !h.Less(j1, j2) {
            j = j2 // = 2*i + 2  // right child
        }
        // 如果最小的子节点不小于父节点，则已经满足最小堆条件，退出
        if !h.Less(j, i) {
            break
        }
        // 如果最小的子节点小于父节点，则交换这两个节点
        h.Swap(i, j)
        // 让父节点继续下沉
        i = j
    }
    return i > i0
}

up让一个节点上升：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func up(h Interface, j int) {
    for {
        // i为父节点下标
        i := (j - 1) / 2 // parent
        // 如果该节点不小于父节点，则满足最小堆条件，退出
        if i == j || !h.Less(j, i) {
            break
        }
        // 如果该节点小于父节点，则交换这两个节点
        h.Swap(i, j)
        // 让该节点继续上升
        j = i
    }
}

#Init

1
2
3
4
5
6
7
func Init(h Interface) {
    n := h.Len()
    // 最后一个节点下表为n-1，因此其父节点为(n-1-1)/2，即n/2-1
    for i := n/2 - 1; i >= 0; i-- {
        down(h, i, n)
    }
}

#Push

1
2
3
4
func Push(h Interface, x interface{}) {
    h.Push(x)
    up(h, h.Len()-1)
}

Push的时候，先把新元素放置在结尾，然后让其上升。

#Pop

1
2
3
4
5
6
func Pop(h Interface) interface{} {
    n := h.Len() - 1
    h.Swap(0, n)
    down(h, 0, n)
    return h.Pop()
}

Pop的时候，先把根节点和最后一个节点交换位置，然后让新的根节点下降。注意这里down的第三个参数是n的值为h.Len() - 1，因此新的根节点下降的过程中，原先的根节点位于最后的位置，不受影响。

#Remove

1
2
3
4
5
6
7
8
9
func Remove(h Interface, i int) interface{} {
    n := h.Len() - 1
    if n != i {
        h.Swap(i, n)
        down(h, i, n)
        up(h, i)
    }
    return h.Pop()
}

Remove操作与Pop非常类似，先将需要移除的节点和最后一个节点交换位置，然后同时进行down和up操作。

#Fix

1
2
3
4
5
func Fix(h Interface, i int) {
    if !down(h, i, h.Len()) {
        up(h, i)
    }
}

当某个节点的值改变后，通过Fix操作来调整堆的结构。该操作实际上也是同时进行了down和up操作。

与先移除旧节点再添加新节点相比，Fix操作的复杂度要低一些。

container/list

list定义了一个双向链表。

#Element

list的元素定义如下：

1
2
3
4
5
6
7
8
9
10
11
type Element struct {
    // Next and previous pointers in the doubly-linked list of elements.
    // The front of the list has prev = nil, and the back has next = nil.
    next, prev *Element

    // The list to which this element belongs.
    list *List

    // The contents of this list element.
    Value interface{}
}

Element定义了Next()和Prev()方法，定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Next returns the next list element or nil.
func (e *Element) Next() *Element {
    if p := e.next; e.list != nil && p != &e.list.root {
        return p
    }
    return nil
}

// Prev returns the previous list element or nil.
func (e *Element) Prev() *Element {
    if p := e.prev; e.list != nil && p != &e.list.root {
        return p
    }
    return nil
}

总的来说，这两个方法的执行逻辑是：

  • 如果该元素在某一个链表上，且其前一个（后一个）元素不是链表的根元素，则返回其前一个（后一个）元素
  • 其它情况下，即如果该元素不属于任何链表，或者其前一个（后一个）元素为链表的根元素，则返回nil（即：链表的根元素只起到一个占位作用，而并不会存储数据值）

#List

通过New()方法可以创建一个新的链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
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
}

// Init initializes or clears list l.
func (l *List) Init() *List {
    l.root.next = &l.root
    l.root.prev = &l.root
    l.len = 0
    return l
}

// New returns an initialized list.
func New() *List { return new(List).Init() }

可以看到，New()实际上调用了Init()方法，主要作用就是初始化一个链表的根元素。

事实上，List是一个首尾相连的环状结构，只不过由于根元素只是起到了占位作用，对外是不可见的，因此对于用户操作来说，看到的是一个链状结构。

其相关操作以及源码都比较简单，不做赘述。下面是一个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
package main

import (
    "container/list"
    "fmt"
)

func main() {
    l := list.New()

    l.PushBack("a")
    printList(l) // a

    l.PushBack("b")
    printList(l) // a b

    l.PushFront("c")
    printList(l) // c a b

    fmt.Println(l.Front().Value) // c
    fmt.Println(l.Back().Value)  // b
    fmt.Println(l.Len())         // 3

    l.MoveToBack(l.Front())
    printList(l) // a b c

    l.MoveToFront(l.Back())
    printList(l) // c a b

    l.Remove(l.Back())
    printList(l) // c a
}

func printList(l *list.List) {
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Print(e.Value, " ")
    }
    fmt.Println()
}

container/ring

ring是一个首尾相连的list。其中每一个元素的定义如下：

1
2
3
4
type Ring struct {
    next, prev *Ring
    Value      interface{} // for use by client; untouched by this library
}

通过New方法可以创建一个特定大小的ring，例如：

1
r := ring.New(5)

#Next 和 Prev

Next和Prev操作比较简单，不做赘述。

#Len

通过遍历整个ring来统计元素的个数。

#Move

Move操作用来获取某个元素之前或者之后的某个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func (r *Ring) Move(n int) *Ring {
    if r.next == nil {
        return r.init()
    }
    switch {
    // 向前找
    case n < 0:
        for ; n < 0; n++ {
            r = r.prev
        }
    // 向后找
    case n > 0:
        for ; n > 0; n-- {
            r = r.next
        }
    }
    return r
}

Link操作可以将两个ring连接起来，比较简单，不做赘述。

Unlink可以移除某个元素后面的若干个元素：

1
2
3
4
5
6
func (r *Ring) Unlink(n int) *Ring {
    if n <= 0 {
        return nil
    }
    return r.Link(r.Move(n + 1))
}

Unlink操作实际上是将起始点与移除后的下一个点进行了Link操作，这样中间需要被移除的点就不再出现在该ring中了。