LOADING

Follow me

Golang漫谈之heap
11月 22 2019|

Golang漫谈之heap

除了《Kubernetes GO》系列之外,对于golang相关知识,同时准备了《Golang 漫谈》以增雅趣,不足之处,万望海涵,在此特别感谢雨痕的Golang 源码剖析
Go语言的OOP,接口,接口的组合,基础库的函数及接口如何抽象设计,这些东西在Go的Heap源码及演示例子处理中,都有很好的展示.

[

heap是Golang内置的标准库封装,该文章主要介绍,以下内容:

  • heap介绍及范例
  • heap解析

一、heap介绍及范例

堆就是用数组实现的二叉树,所有它没有使用父指针或者子指针。堆根据“堆属性”来排序,“堆属性”决定了树中节点的位置。

堆的常用方法:

  • 构建优先队列

  • 支持堆排序

  • 快速找出一个集合中的最小值(或者最大值)

1.1 堆属性

堆分为两种:最大堆和最小堆,两者的差别在于节点的排序方式。

在最大堆中,父节点的值比每一个子节点的值都要大。在最小堆中,父节点的值比每一个子节点的值都要小。这就是所谓的“堆属性”,并且这个属性对堆中的每一个节点都成立。

heap1

这是一个最大堆,,因为每一个父节点的值都比其子节点要大。10比7和2都大。7比5和1都大。

根据这一属性,那么最大堆总是将其中的最大值存放在树的根节点。而对于最小堆,根节点中的元素总是树中的最小值。堆属性非常的有用,因为堆常常被当做优先队列使用,因为可以快速的访问到“最重要”的元素。

堆的根节点中存放的是最大或者最小元素,但是其他节点的排序顺序是未知的。例如,在一个最大堆中,最大的那一个元素总是位于 index 0 的位置,但是最小的元素则未必是最后一个元素。–唯一能够保证的是最小的元素是一个叶节点,但是不确定是哪一个。

1.2 堆和普通树的区别

堆并不能取代二叉搜索树,它们之间有相似之处也有一些不同。我们来看一下两者的主要差别:

  • 节点的顺序。在二叉搜索树中,左子节点必须比父节点小,右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小,而在最小堆中,它们都必须比父节点大。

  • 内存占用。普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配额为是我内存。堆仅仅使用一个数据来村塾数组,且不使用指针。

  • 平衡。二叉搜索树必须是“平衡”的情况下,其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据,或者使用 AVL 树或者红黑树,但是在堆中实际上不需要整棵树都是有序的。我们只需要满足对属性即可,所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。

  • 搜索。在二叉树中搜索会很快,但是在堆中搜索会很慢。在堆中搜索不是第一优先级,因为使用堆的目的是将最大(或者最小)的节点放在最前面,从而快速的进行相关插入、删除操作。

来自数组的树

用数组来实现树相关的数据结构也许看起来有点古怪,但是它在时间和空间山都是很高效的。我们准备将上面的例子中的树这样存储:

1
[ 10, 7, 2, 5, 1 ]

就这多!我们除了一个简单的数组以外,不需要任何额外的空间。

如果我们不允许使用指针,那么我们怎么知道哪一个节点是父节点,哪一个节点是它的子节点呢?问得好!节点在数组中的位置index 和它的父节点已经子节点的索引之间有一个映射关系。

如果 i 是节点的索引,那么下面的公式就给出了它的父节点和子节点在数组中的位置:

1
2
3
parent(i) = floor((i - 1)/2)
left(i) = 2i + 1
right(i) = 2i + 2

注意 right(i) 就是简单的 left(i) + 1。左右节点总是处于相邻的位置。

我们将写公式放到前面的例子中验证一下。

Node Array index (i) Parent index Left child Right child
10 0 -1 1 2
7 1 0 3 4
2 2 0 5 6
5 3 1 7 8
1 4 1 9 10

根节点(10)没有父节点,因为 -1 不是一个有效的数组索引。同样,节点 (2),(5)和(1) 没有子节点,因为这些索引已经超过了数组的大小,所以我们在使用这些索引值的时候需要保证是有效的索引值。

在最大堆中,父节点的值总是要大于(或者等于)其子节点的值。这意味下面的公式对数组中任意一个索引i都成立:array[parent(i)] >= array[i]

可以用上面的例子来验证一下这个堆属性。

如你所见,这些公式允许我们不使用指针就可以找到任何一个节点的父节点或者子节点。事情比简单的去掉指针要复杂,但这就是交易:我们节约了空间,但是要进行更多计算。幸好这些计算很快并且只需要O(1)的时间。

理解数组索引和节点位置之间的关系非常重要。这里有一个更大的堆,它有15个节点被分成了4层:

树

图片中的数字不是节点的值,而是存储这个节点的数组索引!这里是数组索引和树的层级之间的关系:

数组

由上图可以看到,数组中父节点总是在子节点的前面。注意这个方案与一些限制。你可以在普通二叉树中按照下面的方式组织数据,但是在堆中不可以:

一般树

在堆中,在当前层级所有的节点都已经填满之前不允许开是下一层的填充,所以堆总是有这样的形状:

heapshap

注意:你可以使用普通树来模拟堆,但是那对空间是极大的浪费。

假设我们有这样一个数组:

1
[ 10, 14, 25, 33, 81, 82, 99 ]

这是一个有效的堆吗?答案是 yes !一个从低到高有序排列的数组是以有效的最小堆,我们可以将这个堆画出来:

sortedArray

堆属性适用于每一个节点,因为父节点总是比它的字节点小。(你也可以验证一下:一个从高到低有序排列的数组是一个有效的最大堆)

注意:并不是每一个最小堆都是一个有序数组!要将堆转换成有序数组,需要使用堆排序。

1.3 堆的用途

有两个原始操作用于保证插入或删除节点以后堆是一个有效的最大堆或者最小堆:

  • shiftUp(): 如果一个节点比它的父节点大(最大堆)或者小(最小堆),那么需要将它同父节点交换位置。这样是这个节点在数组的位置上升。
  • shiftDown(): 如果一个节点比它的子节点小(最大堆)或者大(最小堆),那么需要将它向下移动。这个操作也称作“堆化(heapify)”。

shiftUp 或者 shiftDown 是一个递归的过程,所以它的时间复杂度是 O(log n)。

基于这两个原始操作还有一些其他的操作:

  • insert(value): 在堆的尾部添加一个新的元素,然后使用 shiftUp 来修复对。
  • remove(): 移除并返回最大值(最大堆)或者最小值(最小堆)。为了将这个节点删除后的空位填补上,需要将最后一个元素移到根节点的位置,然后使用 shiftDown 方法来修复堆。
  • removeAtIndex(index): 和 remove() 一样,差别在于可以移除堆中任意节点,而不仅仅是根节点。当它与子节点比较位置不时无序时使用 shiftDown(),如果与父节点比较发现无序则使用 shiftUp()。
  • replace(index, value):将一个更小的值(最小堆)或者更大的值(最大堆)赋值给一个节点。由于这个操作破坏了堆属性,所以需要使用 shiftUp() 来修复堆属性。
    上面所有的操作的时间复杂度都是 O(log n),因为 shiftUp 和 shiftDown 都很费时。还有少数一些操作需要更多的时间:

  • search(value):堆不是为快速搜索而建立的,但是 replace() 和 removeAtIndex() 操作需要找到节点在数组中的index,所以你需要先找到这个index。时间复杂度:O(n)。

  • buildHeap(array):通过反复调用 insert() 方法将一个(无序)数组转换成一个堆。如果你足够聪明,你可以在 O(n) 时间内完成。
  • 堆排序:由于堆就是一个数组,我们可以使用它独特的属性将数组从低到高排序。时间复杂度:O(n lg n)。

堆还有一个 peek() 方法,不用删除节点就返回最大值(最大堆)或者最小值(最小堆)。时间复杂度 O(1) 。

注意:到目前为止,堆的常用操作还是使用 insert() 插入一个新的元素,和通过 remove()移除最大或者最小值。两者的时间复杂度都是O(log n)。其其他的操作是用于支持更高级的应用,比如说建立一个优先队列。

插入

我们通过一个插入例子来看看插入操作的细节。我们将数字16插入到这个堆中:

heap1

堆的数组是: [ 10, 7, 2, 5, 1 ]
第一股是将新的元素插入到数组的尾部。数组变成:
[ 10, 7, 2, 5, 1, 16 ]
相应的树变成了:

Insert1

16 被添加最后一行的第一个空位。
不行的是,现在堆属性不满足,因为2在16的上面,我们需要将大的数字在上面(这是一个最大堆)
为了恢复堆属性,我们需要交换16和2。

Insert2

现在还没有完成,因为 10 也比 16 小。我们继续交换我们的插入元素和它的父节点,直到它的父节点比它大或者我们到达树的顶部。这就是所谓的 shift-up,每一次插入操作后都需要进行。它将一个太大或者太小的数字“浮起”到树的顶部。
最后我们得到的堆:

Insert3

现在每一个父节点都比它的子节点大。

删除根节点

我们将这个树中的 (10) 删除:

Heap1

现在顶部有一个空的节点,怎么处理?

Remove1

当插入节点的时候,我们将新的值返给数组的尾部。现在我们来做相反的事情:我们取出数组中的最后一个元素,将它放到树的顶部,然后再修复堆属性。

Remove2

现在来看怎么 shift-down (1)。为了保持最大堆的堆属性,我们需要树的顶部是最大的数据。现在有两个数字可用于交换 7 和 2。我们选择这两者中的较大者称为最大值放在树的顶部,所以交换 7 和 1,现在树变成了:

Remove3

继续堆化直到该节点没有任何子节点或者它比两个子节点都要大为止。对于我们的堆,我们只需要再有一次交换就恢复了堆属性:

Remove4

删除任一节点

绝大多数时候你需要删除的是堆的根节点,因为这就是堆的设计用途。

但是,删除任意节点也很有用。这是 remove() 的通用版本,它可能会使用到 shiftDown 和 shiftUp。

我们还是用前面的例子,删除 (7):

Heap1

对应的数组是:[ 10, 7, 2, 5, 1 ]

你知道,移除一个元素会破坏最大堆或者最小堆属性。我们需要将删除的元素和最后一个元素交换:
[ 10, 1, 2, 5, 7 ]

最后一个元素就是我们需要返回的元素;然后调用 removeLast() 来将它删除。 (1) 比它的子节点小,所以需要 shiftDown() 来修复。

然而,shift down 不是我们要处理的唯一情况。也有可能我们需要 shift up。考虑一下从下面的堆中删除 (5) 会发生什么:

Remove5

现在 (5) 和 (8) 交换了。因为 (8) 比它的父节点大,我们需要 shiftUp()。


二、heap解析

2.1 goroutine通信

heap包对任意实现了heap接口的类型提供堆操作。(小根)堆是具有“每个节点都是以其为根的子树中最小值”属性的树。树的最小元素在根部,为index 0.
heap是常用的实现优先队列的方法。要创建一个优先队列,实现一个具有使用(负的)优先级作为比较的依据的Less方法的Heap接口,如此一来可用Push添加项目而用Pop取出队列最高优先级的项目。

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

可以看出,这个堆结构继承自sort.Interface, 而sort.Interface,需要实现三个方法:

  • Len() int
  • Less(i, j int) bool
  • Swap(i, j int)

再加上堆接口定义的两个方法:

  • Push(x interface{})
  • Pop() interface{}。

故只要实现了这五个方法,变定义了一个堆。

任何实现了本接口的类型都可以用于构建最小堆。最小堆可以通过heap.Init建立,数据是递增顺序或者空的话也是最小堆。最小堆的约束条件是:

!h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()

注意接口的Push和Pop方法是供heap包调用的,请使用heap.Push和heap.Pop来向一个堆添加或者删除元素。

  • func Fix(h Interface, i int) // 在修改第i个元素后,调用本函数修复堆,比删除第i个元素后插入新元素更有效率。复杂度O(log(n)),其中n等于h.Len()。
  • func Init(h Interface) //初始化一个堆。一个堆在使用任何堆操作之前应先初始化。Init函数对于堆的约束性是幂等的(多次执行无意义),并可能在任何时候堆的约束性被破坏时被调用。本函数复杂度为O(n),其中n等于h.Len()。
  • func Pop(h Interface) interface{} //删除并返回堆h中的最小元素(不影响约束性)。复杂度O(log(n)),其中n等于h.Len()。该函数等价于Remove(h, 0)。
  • func Push(h Interface, x interface{}) //向堆h中插入元素x,并保持堆的约束性。复杂度O(log(n)),其中n等于h.Len()。
  • func Remove(h Interface, i int) interface{} //删除堆中的第i个元素,并保持堆的约束性。复杂度O(log(n)),其中n等于h.Len()。

利用heap创建一个优先级队列:

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
package main

import (
"container/heap"
"fmt"
)

// 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
}
// This example inserts several ints into an IntHeap, checks the minimum,
// and removes them in order of priority.
func main() {
h := &IntHeap{2, 1, 5, 100, 3, 6, 4, 5}
heap.Init(h)
heap.Push(h, 3)
heap.Fix(h, 3)
fmt.Printf("minimum: %d\n", (*h)[0])
for h.Len() > 0 {
fmt.Printf("%d ", heap.Pop(h))
}
}

利用heap创建一个优先级队列

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// This example demonstrates a priority queue built using the heap interface.
package main

import (
"container/heap"
"fmt"
)

// An Item is something we manage in a priority queue.
type Item struct {
value string // The value of the item; arbitrary.
priority int // The priority of the item in the queue.
// The index is needed by update and is maintained by the heap.Interface methods.
index int // The index of the item in the heap.
}

// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
// We want Pop to give us the highest, not lowest, priority so we use greater than here.
return pq[i].priority > pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].index = i
pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
n := len(*pq)
item := x.(*Item)
item.index = n
*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
item.index = -1 // for safety
*pq = old[0 : n-1]
return item
}

// update modifies the priority and value of an Item in the queue.
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
item.value = value
item.priority = priority
heap.Fix(pq, item.index)
}

// This example creates a PriorityQueue with some items, adds and manipulates an item,
// and then removes the items in priority order.
func main() {
// Some items and their priorities.
items := map[string]int{
"banana": 3, "apple": 2, "pear": 4,
}

// Create a priority queue, put the items in it, and
// establish the priority queue (heap) invariants.
pq := make(PriorityQueue, len(items))
i := 0
for value, priority := range items {
pq[i] = &Item{
value: value,
priority: priority,
index: i,
}
i++
}
heap.Init(&pq)

// Insert a new item and then modify its priority.
item := &Item{
value: "orange",
priority: 1,
}
heap.Push(&pq, item)
pq.update(item, item.value, 5)

// Take the items out; they arrive in decreasing priority order.
for pq.Len() > 0 {
item := heap.Pop(&pq).(*Item)
fmt.Printf("%.2d:%s \n", item.priority, item.value)
}
}

自定义的类,实现相关接口后,交由heap.Init()去构建堆.

  • 从堆中Pop()后,数据就被从heap中移除了.
  • 升降序由Less()来决定.
  • 自定义类也可以直接用Sort来排序,因为实现了相关接口.

后续

heap在kubernetes scheduler相关内容涉及,将会在后续推出。


参考资料

zouyee wechat

微信扫一扫
关注该公众号

0%