version: 1.10

package heap

import "container/heap"

概述

heap 包为任何实现了 heap.Interface 的类型提供对 heap 的操作。heap 是一种叫做最小树的数据结构，特点是每个结点都是子树的最小值。

树里的最小元素位于根结点，索引是0。

heap 是实现优先队列的常见方法。要建立一个优先队列，需要实现 Heap 接口，并在 Less 方法中以（负的）优先级作为排序的条件。下面的例子包含一个对应的实现，example_pq_test.go 文件包含完整的源码。

例子:

  1. // 这个例子演示了一个使用 heap 接口构建的整数堆。
  2. package heap_test
  4. import (
  5.     "container/heap"
  6.     "fmt"
  7. )
  9. // IntHeap 是元素为整数的最小堆。
  10. type IntHeap []int
  12. func (h IntHeap) Len() int           { return len(h) }
  13. func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
  14. func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
  16. func (h *IntHeap) Push(x interface{}) {
  17.     // Push and Pop 方法使用指针作为接收者是因为它们修改切片的长度，
  18.     // 而不只是内容。
  19.     *h = append(*h, x.(int))
  20. }
  22. func (h *IntHeap) Pop() interface{} {
  23.     old := *h
  24.     n := len(old)
  25.     x := old[n-1]
  26.     *h = old[0 : n-1]
  27.     return x
  28. }
  30. // 这个例子插入若干整数到 IntHeap ，检查堆的最小值，
  31. // 然后按照优先级顺序删除它们。
  32. func Example_intHeap() {
  33.     h := &IntHeap{2, 1, 5}
  34.     heap.Init(h)
  35.     heap.Push(h, 3)
  36.     fmt.Printf("minimum: %d\n", (*h)[0])
  37.     for h.Len() > 0 {
  38.         fmt.Printf("%d ", heap.Pop(h))
  39.     }
  40.     // Output:
  41.     // minimum: 1
  42.     // 1 2 3 5
  43. }

例子:

  1. // 这个例子演示了一个使用 heap 接口构建的优先队列。
  2. package heap_test
  4. import (
  5.     "container/heap"
  6.     "fmt"
  7. )
  9. // Item 是优先队列里的元素。
  10. type Item struct {
  11.     value    string // 元素的值，任何内容都行。
  12.     priority int    // 本元素在队列里的优先级。
  13.     // index 被 update 方法使用，并被 heap.Interface 的方法维护。
  14.     index int // 元素在堆里的索引。
  15. }
  17. // PriorityQueue 类型实现了 heap.Interface 并存储数据。
  18. type PriorityQueue []*Item
  20. func (pq PriorityQueue) Len() int { return len(pq) }
  22. func (pq PriorityQueue) Less(i, j int) bool {
  23.     // 我们想要 Pop 函数获得最高的，而不是最低的，优先级所以我们这里使用大于号。
  24.     return pq[i].priority > pq[j].priority
  25. }
  27. func (pq PriorityQueue) Swap(i, j int) {
  28.     pq[i], pq[j] = pq[j], pq[i]
  29.     pq[i].index = i
  30.     pq[j].index = j
  31. }
  33. func (pq *PriorityQueue) Push(x interface{}) {
  34.     n := len(*pq)
  35.     item := x.(*Item)
  36.     item.index = n
  37.     *pq = append(*pq, item)
  38. }
  40. func (pq *PriorityQueue) Pop() interface{} {
  41.     old := *pq
  42.     n := len(old)
  43.     item := old[n-1]
  44.     item.index = -1 // for safety
  45.     *pq = old[0 : n-1]
  46.     return item
  47. }
  49. // update 方法修改队列里元素的优先级和值。
  50. func (pq *PriorityQueue) update(item *Item, value string, priority int) {
  51.     item.value = value
  52.     item.priority = priority
  53.     heap.Fix(pq, item.index)
  54. }
  56. // 这个例子创建一个有若干元素的 PriorityQueue ，添加并操作一个元素，
  57. // 然后按照优先级顺序移除所有元素。
  58. func Example_priorityQueue() {
  59.     // 若干带有优先级的元素。
  60.     items := map[string]int{
  61.         "banana": 3, "apple": 2, "pear": 4,
  62.     }
  64.     // 创建一个优先队列，把 items 放进去，然后建立优先队列（堆）的不变量。
  65.     pq := make(PriorityQueue, len(items))
  66.     i := 0
  67.     for value, priority := range items {
  68.         pq[i] = &Item{
  69.             value:    value,
  70.             priority: priority,
  71.             index:    i,
  72.         }
  73.         i++
  74.     }
  75.     heap.Init(&pq)
  77.     // 插入一个新的元素，然后修改它的优先级。
  78.     item := &Item{
  79.         value:    "orange",
  80.         priority: 1,
  81.     }
  82.     heap.Push(&pq, item)
  83.     pq.update(item, item.value, 5)
  85.     // 取出所有元素，它们应该按照优先级递减的顺序出来。
  86.     for pq.Len() > 0 {
  87.         item := heap.Pop(&pq).(*Item)
  88.         fmt.Printf("%.2d:%s ", item.priority, item.value)
  89.     }
  90.     // Output:
  91.     // 05:orange 04:pear 03:banana 02:apple
  92. }

索引

例子

文件

heap.go

func Fix 

  1. func Fix(h Interface, i int)

Fix 函数在索引 i 的元素的值变化后重新构建堆。改变索引 i 处元素的值并调用 Fix 函数等价于调用 Remove(h, i) 然后调用 Push 函数来插入新的数据，不过代价较小。算法的时间复杂度是 O(log(n))，这里 n 等于 h.Len()。

func Init 

  1. func Init(h Interface)

堆必须初始化后才能使用。Init 函数会初始化堆的不变量，并应该在堆的不变量无效时调用。算法的时间复杂度是 O(n)，这里 n 等于 h.Len()。

func Pop 

  1. func Pop(h Interface) interface{}

Pop 函数从堆里移除值最小的元素（通过 Less 方法）并返回该元素。算法的时间复杂度是 O(log(n))，这里 n 等于 h.Len()。它等价于 Remove(h, 0)。

func Push 

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

Push 函数添加元素 x 到堆里。算法的时间复杂度是 O(log(n))，这里 n 等于 h.Len()。

func Remove 

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

Remove 函数从堆里移除索引 i 处的元素。算法的时间复杂度是 O(log(n))，这里 n 等于 h.Len()。

type Interface 

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

任何实现了 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()

注意：这个接口里的 Push 和 Pop 方法是heap包内部实现调用。如果要向堆里添加或移除数据，请使用 heap.Push 和 heap.Pop 函数。