Src code from https://golang.org/src/container/heap/heap.go

Heap

Package heap provides heap operations for any type that implements heap.Interface. A heap is a tree with the property that each node is the minimum-valued node in its subtree.

The minimum element in the tree is the root, at index 0.

A heap is a common way to implement a priority queue. To build a priority queue, implement the Heap interface with the (negative) priority as the ordering for the Less method, so Push adds items while Pop removes the highest-priority item from the queue.

Interface

Any type that implements heap.Interface may be used as a min-heap with the following invariants (established after Init has been called or if the data is empty or sorted):

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

Note that Push and Pop in this interface are for package heap’s implementation to call. To add and remove things from the heap, use heap.Push and heap.Pop.

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

Init Heap

A heap must be initialized before any of the heap operations can be used. Init is idempotent with respect to the heap invariants and may be called whenever the heap invariants may have been invalidated. Its 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)
    }
}

Swim up

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

Sink down

func down(h Interface, i0, n int) bool {
    i := i0
    for {
        j1 := 2*i + 1
        if j1 >= n || j1 < 0 {
            break
        }
        j := j1
        if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
            j = j2
        }
        if !h.Less(j, i) {
            break
        }
         h.Swap(i, j)
         i = j
    }
    return i > i0
}

push

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

Pop removes the minimum element (according to Less) from the heap and returns it. The complexity is O(log(n)) where n = h.Len(). It 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()
}

Fix

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().

func Fix(h Interface, i int) {
    if !down(h, i, h.Len()) {
        up(h, i)
    }
}

Remove

Remove removes 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()-1
    if n != i {
        h.Swap(i, n)
        if !down(h, i, n) {
            up(h, i)
        }
    }
    return n.Pop()
}

Priority Queue

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 ", item.priority, item.value)
    }
}