Heap implementation in Go

heap最常见的用途就是实现优先级队列，Java、C++库函数中都有PriorityQueue这种数据结构，而Go中的Heap却与众不同。

接口

heap包中提供了这样一个接口：

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

以及Push和Pop两个导出的函数：

// Push pushes the element x onto the heap.
// The complexity is O(log n) where n = h.Len().
func Push(h Interface, x interface{}) {
	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 := h.Len() - 1
	h.Swap(0, n)
	down(h, 0, n)
	return h.Pop()
}

令人困惑的是：这两个函数不是heap.Interface的两个方法，那要如何使用Go提供的Heap呢？

栗子

heap包中Pop和Push函数都要接受heap.Interface类型的参数，因此，要想使用这两个函数，必须先自定义类并实现heap.Interface定义的方法。

默认建立小顶堆，如果想建立大顶堆，可以重写Heap的Less方法。

type Heap []int

// sort.Interface
func (h Heap) Len() int {
	return len(h)
}

// sort.Interface
func (h Heap) Less(i, j int) bool {
	return h[i] < h[j]
}

// sort.Interface
func (h Heap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

// add x as element Len()
func (h *Heap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

// remove and return element Len() - 1.
func (h *Heap) Pop() interface{} {
	v := (*h)[h.Len()-1]
	*h = (*h)[:h.Len()-1]
	return v
}

要注意heap.Interface的Pop和Push方法并非是最终暴露在外让用户调用的接口，而是让heap包去调用的接口。

Push方法在heap对应底层数据结构（数组）的末尾处加上一个元素，Pop方法删除并返回最后的元素。

---

上面所做的都是heap包所需的，完整的heap还需要我们提供额外的接口给用户，这一过程需要借助heap包的Push和Pop（不是我们写的Push和Pop）来完成：

type Heap []int

func NewHeap(x ...int) *Heap {
   var hp Heap
   hp = make([]int, len(x))
   copy(hp, x)
   heap.Init(&hp)
   return &hp
}

func (h *Heap) Add(x int) {
   heap.Push(h, x)
}

func (h *Heap) Get() int {
   return heap.Pop(h).(int)
}

Priority Queue

可以借助heap来实现Priority Queue：

// 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]
	old[n-1] = nil  // avoid memory leak
	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 Example_priorityQueue() {
	// 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 ", item.priority, item.value)
	}
	// Output:
	// 05:orange 04:pear 03:banana 02:apple
}

Detail

堆（英语：Heap）是计算机科学中的一种特别的完全二叉树。在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干节点，则此二叉树为完全二叉树（Complete Binary Tree）。

对于堆这种数据结构，主要考虑如何建堆（大顶堆或小顶堆）、添加元素或者获取堆顶元素后要维持堆的形态。

可以参考：堆排序

建堆

对于一颗完全二叉树，最后一个有孩子的节点的下标是：n/2-1，对该节点以及之前的节点进行down操作，即可建成堆。

// Init establishes the heap invariants required by the other routines in this package.
// Init is idempotent with respect to the heap invariants
// and may be called whenever the heap invariants may have been invalidated.
// The complexity is O(n) where n = h.Len().
func Init(h Interface) {
	// heapify
	n := h.Len()
	for i := n/2 - 1; i >= 0; i-- {
		down(h, i, n)
	}
}

func down(h Interface, i0, n int) {
    // parent
	i := i0
    // 也可以用递归的方式
	for {
        // left child
		j1 := 2*i + 1
        // if left child does not exist
		if j1 >= n || j1 < 0 {
			break
		}
		j := j1 // left child
        // if right child exist and smaller than left child
		if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
			j = j2 // = 2*i + 2  // right child
		}
		if !h.Less(j, i) {
			break
		}
        // parent swap with the smaller child
		h.Swap(i, j)
		i = j
	}
}

插入删除

插入：将元素添加到数组末尾，执行up操作

删除：将堆顶元素和末尾元素互换，数组末尾元素即为索取，再对堆顶元素执行down操作维持堆的形态

// Push pushes the element x onto the heap.
// The complexity is O(log n) where n = h.Len().
func Push(h Interface, x interface{}) {
	h.Push(x)
	up(h, h.Len()-1)
}

func up(h Interface, j int) {
	for {
		i := (j - 1) / 2 // parent
		if i == j || !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		j = i
	}
}

// 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 := h.Len() - 1
	h.Swap(0, n)
	down(h, 0, n)
	return h.Pop()
}