go与堆

概述

堆(heap)又被为优先队列(priority queue)。尽管名为优先队列,但堆并不是队列。回忆一下,在队列中,我们可以进行的限定操作是进队列和出队列。出队列是按照进入队列的先后顺序来取出元素。而在堆中,我们不是按照元素进入队列的先后顺序取出元素的,而是按照元素的优先级取出元素。

堆的一个经典的实现是完全二叉树(complete binary tree)。这样实现的堆成为二叉堆(binary heap)。完全二叉树是增加了限定条件的二叉树。假设一个二叉树的深度为n。为了满足完全二叉树的要求,该二叉树的前n-1层必须填满,第n层也必须按照从左到右的顺序被填满

container/heap

container/heap为所有实现了heap.Interface的类型提供堆操作。一个堆即是一棵树,这棵树的每个节点的值都比它的子节点的值要小,而整棵树最小的值位于树根root,也即是索引0的位置上。

Fix 函数

1
func Fix(h Interface, i int)

在索引i上的元素的值发生变化之后,重新修复堆的有序性。先修改索引i上的元素的值然后再执行Fix,跟先调用Remove(h, i)然后再使用 Push 操作将新值重新添加到堆里面的做法具有同等的效果,但前者所需的计算量稍微要少一些。

Fix函数的复杂度为O(log(n)),其中n等于h.Len()

Init 函数

1
func Init(h Interface)

在执行任何堆操作之前,必须对堆进行初始化。Init操作对于堆不变性(invariants)具有幂等性,无论堆不变性是否有效,它都可以被调用。

Init函数的复杂度为O(n),其中 n 等于h.Len()

Pop 函数

1
func Pop(h Interface) interface{}

Pop函数根据Less的结果,从堆中移除并返回具有最小值的元素,等同于执行Remove(h, 0)

Pop函数的复杂度为O(log(n)), 其中n等于h.Len()

Push 函数

1
func Push(h Interface, x interface{})

Push函数将值为x的元素推入到堆里面,该函数的复杂度为O(log(n)),其中n等于h.Len()

Remove 函数

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

Remove函数将移除堆中索引为i的元素,该函数的复杂度为O(log(n)),其中 n 等于h.Len()

Interface 类型

任何实现了heap.Interface接口的类型,都可以用作带有以下不变性的最小堆,(换句话说,这个堆在为空、已排序或者调用Init 之后,应该具有以下性质):

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

注意, 这个接口中的PushPop都是由heap包的实现负责调用的。因此用户在向堆添加元素又或者从堆中移除元素时,需要使用heap.Push以及heap.Pop

1
2
3
4
5
type Interface interface {
sort.Interface
Push(x interface{}) // 将 x 添加为元素 Len()
Pop() interface{} // 移除并返回元素 Len() - 1
}

Example

可以先看一下container/heap官方文档的两个范例,整数堆和优先队列。整数堆是最基本的运用,优先队列在业务中是一个常用的场景。

数组中的第K个最大元素

这个是leetcode中的一道题,就可以利用整数堆来减少排序元素。

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
import "container/heap"

// intHeap 是一个由整数组成的最小堆。
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 和 Pop 使用 pointer receiver 作为参数,
// 因为它们不仅会对切片的内容进行调整,还会修改切片的长度。
*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
}

// min 堆最小元素的值
func (h *intHeap) min() int {
if len(*h) > 0 {
return (*h)[0]
}
return -1
}

// 题解
func findKthLargest(nums []int, k int) int {
// 把前k个元素初始化到堆,此时索引0是当前第k个最大元素,也就是h.min()
h := intHeap(nums[:k])
heap.Init(&h)

for i := k; i < len(nums); i++ {
// 当之后的元素比h.min()小,忽略,否则pop出最小元素,push进新元素
if nums[i] > h.min() {
heap.Pop(&h)
heap.Push(&h, nums[i])
}
}
return h.min()
}

可以看下提交后的排名。
leetcode提交详情