go语言源码解读之数据结构堆

概述

堆(heap)，是一种计算中常用的数据结构。本文我们将探讨对的特性、实现细节以及实际应用场景。

基本概念

堆是一种特殊的完全二叉树。堆分为大顶堆与小顶堆。

• 大顶堆的特点是，父节点的值总是大于或等于其子节点的值。

• 小顶堆的特点是，父节点的值总是小于或等于其子节点的值。

小顶堆的首个元素是整个堆中的最小值，大顶堆的首个元素是整个堆的最大值，利用这种特性，能够快速的访问和提取一组数据中的最小或最大值的元素。

(图片来源于网络，如有侵权请联系纠正)

如果用数组方式实现堆，那么可以用固定规律就可以直接计算出当前节点的父节点的与子节点的索引：

• 父节点的索引计算规则: (i - 1) / 2
• 左子节点的索引的计算规则: i * 2 + 1
• 右子节点的索引的计算规则: i * 2 + 2

(图片来源于网络，如有侵权请联系纠正)

补充：完全二叉树的定义

如果一个二叉树最多只有最下面的两层节点度数可以小于2，并且最下面一层的节点都集中在该层最左边的连续位置上，则此二叉树称做完全二叉树（complete binary tree）

同时注意区分满二叉树与完全二叉树

如果一个二叉树的任何节点，要么是叶子节点，要么左右子树均非空，则这棵二叉树称做满二叉树（full binary tree）

(图片来源于网络，如有侵权请联系纠正)

堆的操作

push

push即入堆操作

1. 先将元素添加到堆的末尾
2. 将元素与父节点比较
3. 假设是小顶堆，如果元素比父节点小，则元素与父节点交换；假设是大顶堆，如果元素比父节点大，则元素与父节点交换
4. 重复此过程，直到元素达到根节点或元素满足对属性

pop

pod即出堆操作

1. 先将根节点与堆的最后一个元素交换
2. 再删除最后一个元素
3. 对新的根节点执行"向下堆化"，维持整个堆的特性。

go语言中的实现

堆可以用数组、链表、二叉搜索树、平衡二叉搜索树等数据结构来实现。但通常选用数组来实现堆，因为可以通过代数方式直接计算出当前节点的父节点、左孩子和右孩子的位置，而不是通过遍历查找父节点与孩子节点的位置。因此它在时间和空间上都是很高效的。

Go语言中堆的实现，可以自己直接实现，也可以利用container/heap包实现。container/heap包提供了堆操作的接口和方法

接下来对container/heap包的源码分析

heap.Interface接口的定义

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

它匿名嵌套了 sort.Interface 接口，sort.Interface的定义如下：

type Interface interface {Len() intLess(i, j int) boolSwap(i, j int)
}

这里继承 sort.Interface 接口，是因为在进行heapify(翻译为"堆化")时，需要使用Less()方法进行节点值的比较，使用Swap()方法进行节点位置之间的交换.

备注：下面的说明默认按小顶堆来说明

// 初始化的初始化
func Init(h Interface) {// heapify(堆化)n := h.Len()// 这里i设置为n/2-1，是因为i的右孩子节点是i*2+2 = (n/2-1)*2+2 = nfor i := n/2 - 1; i >= 0; i-- {down(h, i, n)}
}// Push pushes the element x onto the heap.
// The complexity is O(log n) where n = h.Len().
func Push(h Interface, x interface{}) {// 将x添加到堆中末尾。h.Push(x)// 再对堆末尾的元素，进行"向上堆化"，也就是使新元素必须小于父节点，否则将新元素与父节点交换，一直持续到新元素成为根节点。up(h, h.Len()-1)
}// Pop removes and returns the minimum element (according to Less) from the heap.
// The complexity is O(log n) where n = h.Len().
// Pop is equivalent to Remove(h, 0).
func Pop(h Interface) interface{} {// n是堆最后一个元素的的索引n := h.Len() - 1// 将堆顶与最后一个元素进行交换h.Swap(0, n)// 对堆顶元素(索引为0)，进行"向下堆化"down(h, 0, n)return h.Pop()
}// Remove removes and returns the element at index i from the heap.
// The complexity is O(log n) where n = h.Len().
func Remove(h Interface, i int) interface{} {n := h.Len() - 1if n != i {h.Swap(i, n)if !down(h, i, n) {up(h, i)}}return h.Pop()
}// Fix re-establishes the heap ordering after the element at index i has changed its value.
// Changing the value of the element at index i and then calling Fix is equivalent to,
// but less expensive than, calling Remove(h, i) followed by a Push of the new value.
// The complexity is O(log n) where n = h.Len().
// Fix 的作用是当索引为i的元素的值改变后，需要对i对应的元素，进行“堆化”
func Fix(h Interface, i int) {// 先"向下堆化"，再"向上堆化"if !down(h, i, h.Len()) {up(h, i)}
}

Init(h Interface): 对一个未排序的切片构建堆。这是通过down方法实现的，down方法确保元素下沉到正确的位置，维持堆的性质。for循环的第一个索引i设置为n/2-1，是因为i的右孩子节点是i*2+2 = (n/2-1)*2+2 = n，即数组最后一个元素索引，这里需要注意避免数组索引越界

Push(h Interface, x interface{})：元素被添加到切片的末尾，然后通过up方法上浮到正确的位置。

Pop(h Interface) interface{}：堆顶元素（切片的第一个元素）被移动到切片末尾并返回，然后新的堆顶元素通过down方法恢复堆的性质。

Remove(h Interface, i int) interface{}：类似Pop，但可以移除指定位置的元素。此操作需要综合up和down方法来调整堆。

Fix(h Interface, i int)： 如果堆中某个元素被外部修改了（比如优先级改变），Fix方法会根据这个修改后的新值重新调整堆。

up()方法是heap接口重要的方法，作用是将j索引对应元素，与父节点比较，如果比父节点大，就与父节点交换，重复这个过程一直持续到j对应元素成为根节点或者j对应元素大于父节点。

func up(h Interface, j int) {for {// 通过当前节点j,用代数方式计算出父节点i := (j - 1) / 2 // parent// 如果父节点的索引与当前节点j相等就退出// 或者如果当前节点已经大于登录了父节点，则退出。说明j已经在其应该在的位置了if i == j || !h.Less(j, i) {break}// 否则，此时父节点i比当前节点j小，那么就将父节点与当前节点交互h.Swap(i, j)// 交换后，j的索引指向父节点，等待下一次循环j = i}
}

down()方法是heap接口重要的方法，作用是将i当前节点与孩子比较，如果孩子节点当前节点小，就将孩子节点与当前节点互换。重复这个过程一直到其孩子节点大于当前节点。

func down(h Interface, i0, n int) bool {i := i0for {// j1是左孩子j1 := 2*i + 1// 判断j1左孩子是否从数组溢出if j1 >= n || j1 < 0 { // j1 < 0 after int overflowbreak}j := j1 // left child// j2是i当前节点的右孩子// 如果j2右孩子小于j1左孩子，j就指向右孩子。（这一步的意思是让j指向左右孩子中最小的那个元素）if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {j = j2 // = 2*i + 2  // right child}// 如果j左右孩子(可能是左孩子也可能右孩子)，比i当前节点大，说明i已经满足堆属性了，则退出循环if !h.Less(j, i) {break}// 此时孩子节点小于当前节点，就将当前节点与孩子节点交换h.Swap(i, j)// 交换完后，当前索引指向孩子节点i = j}return i > i0
}

• 时间复杂度

Push/pop： O(LogN)

堆的实际应用场景

• 优先级队列： 例如任务调度器，即按任务优先级大小进行调度的任务调度器。告警系统中，按消息重要性优先发送重要信息等。
• 延时队列: 延迟队列是利用优先级队列，根据元素中的时间戳的先后顺序进行弹出。client-go中的workqueue就是一种延时队列，后面会写篇文章专门分析下workqueue的延时队列的源码，探讨其实现机制
• 堆排序: 利用堆排序，时间复杂度是O(NlogN)
• 网络路由；最短路径算法与最小生成树

利用堆实现优先级队列

优先级队列与堆的关系:

• 优先级队列是一种抽象数据类型，它可以看作是一个队列，但其中的元素是有优先级的。优先级队列的操作通常包括插入元素（通常称为入队），删除具有最高优先级的元素（通常称为出队），以及查看最高优先级的元素（通常称为获取队头元素）。

• 堆是一种具体数据结构。堆的操作通常包括插入元素（通常称为插入），删除具有最高优先级的元素（通常称为删除），以及查看最高优先级的元素（通常称为获取堆顶元素）。

在实际应用中，优先级队列和堆常常被一起使用。例如，操作系统中的任务调度器通常使用优先级队列来管理一组任务，其中的每个任务都有一个优先级。堆可以用于实现优先级队列，例如，我们可以使用最大堆来实现最大优先级队列，使用最小堆来实现最小优先级队列。
总的来说，优先级队列和堆都是处理一组元素的工具，但它们的用途和实现方式有所不同。优先级队列是一种抽象数据类型，而堆是一种数据结构,可以使用堆来实现优先级队列。

示例: 使用go语言的heap.Interface实现一个优先级队里

package mainimport ("container/heap""fmt"
)type Item struct {priority    intname string
}// 优先级队列底层用数组实现
type PriorityQueue []*Item// 先实现heap.Interfach的五个接口Len(),Less(),Swap(),Push(),Pop()
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {// 优先级值(priority)越大越优先(大顶堆), 也就是完全二叉树中，上层的节点的优先级大于下层节点的优先级值return pq[i].priority > pq[j].priority
}
func (pq PriorityQueue) Swap(i, j int) {pq[i], pq[j] = pq[j], pq[i]
}func (pq *PriorityQueue) Push(x interface{}) {Item := x.(*Item)*pq = append(*pq, Item)
}func (pq *PriorityQueue) Pop() interface{} {old := *pqn := len(old)Item := old[n-1]*pq = old[0 : n-1]return Item
}func main() {pq := make(PriorityQueue, 0)heap.Init(&pq)// 插入元素Items := []Item{{1, "low"},{3, "high"},{2, "medium"},}for i := range Items {heap.Push(&pq, &Items[i])}// 按优先级从大到小的弹出元素for pq.Len() > 0 {Item := heap.Pop(&pq).(*Item)fmt.Printf("Item: %s\n", Item.name)}
}-----------输出----------
Item: 高优先级
Item: 中优先级
Item: 低优先级

堆排序

为了简化堆排序的实现，这里借用go标准包container/heap.go中的down函数，能快速实现一个数组的堆化。

heapSort()函数的逻辑是，先将arr建堆，再从arr堆的堆顶依次弹出堆顶元素，并将元素放入res结果数组，完成循环之后res数组就是排序后的数组

package mainimport "fmt"// down 是go标准包container/heap.go中的函数，实现一个数组中某个元素的heapify
func down(h []int, i0, n int) bool {i := i0for {// j1是左孩子j1 := 2*i + 1// 判断j1左孩子是否从数组溢出if j1 >= n || j1 < 0 { // j1 < 0 after int overflowbreak}j := j1 // left child// j2是i当前节点的右孩子// 如果j2右孩子小于j1左孩子，j就指向右孩子。（这一步的意思是让j指向左右孩子中最小的那个元素）if j2 := j1 + 1; j2 < n && (h[j2] < h[j1]) {j = j2 // = 2*i + 2  // right child}// 如果j左右孩子(可能是左孩子也可能右孩子)，比i当前节点大，说明i已经满足堆属性了，则退出循环if h[j] > h[i] {break}// 此时孩子节点小于当前节点，就将当前节点与孩子节点交换h[i], h[j] = h[j], h[i]// 交换完后，当前索引指向孩子节点i = j}return i > i0
}// heapsort 实现对一个数组的堆排序
func heapSort(arr []int) []int {// 构建堆：将数组arr转为一个堆for i := len(arr)/2 - 1; i >= 0; i-- {down(arr, i, len(arr))}// res 用于存放从堆弹出元素并放入结果res := []int{}// 弹出堆的第一个元素，放入res// 然后将最后一个元素放到第一个位置，并重新构建堆for len(arr) > 0 {item := arr[0]res = append(res, item)arr[0] = arr[len(arr)-1]arr = arr[:len(arr)-1]down(arr, 0, len(arr))}return res}func main() {arr := []int{3, 5, 8, 2, 1}arr = heapSort(arr)fmt.Println("after sort:", arr) // after sort: [1 2 3 5 8]arr = []int{3, 3, 3, 3, 3}arr = heapSort(arr)fmt.Println("after sort:", arr) // after sort: [3 3 3 3 3]arr = []int{5, 4, 3, 2, 1}arr = heapSort(arr)fmt.Println("after sort:", arr) // after sort: [1 2 3 4 5]
}

除了自己手写一个堆排序算法之外，可以直接使用go标准库的sort/sort.go包heapSort()，可以快速实现堆排序。算法逻辑实现这里就不再赘述。

// siftDown implements the heap property on data[lo:hi].
// first is an offset into the array where the root of the heap lies.
func siftDown(data Interface, lo, hi, first int) {root := lofor {child := 2*root + 1if child >= hi {break}if child+1 < hi && data.Less(first+child, first+child+1) {child++}if !data.Less(first+root, first+child) {return}data.Swap(first+root, first+child)root = child}
}func heapSort(data Interface, a, b int) {first := alo := 0hi := b - a// Build heap with greatest element at top.for i := (hi - 1) / 2; i >= 0; i-- {siftDown(data, i, hi, first)}// Pop elements, largest first, into end of data.for i := hi - 1; i >= 0; i-- {data.Swap(first, first+i)siftDown(data, lo, i, first)}
}

结语

通过上述分析，我们分析了heap.go源码的实现，进而基于堆我们实现了一个任务优先级队列，我们可以看到Go语言中堆的实现既简洁又高效。从实际工作应用来看，用堆实现的优先级队列使用场景更广泛，需要重点理解和掌握