# Package 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. The Examples include such an
implementation; the file example_pq_test.go has the complete source.

▾ Example (IntHeap)

This example inserts several ints into an IntHeap, checks the minimum,
and removes them in order of priority.

Code:

package heap_test
import (
"container/heap"
"fmt"
)
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{}) {
*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
}
func Example_intHeap() {
h := &IntHeap{2, 1, 5}
heap.Init(h)
heap.Push(h, 3)
fmt.Printf("minimum: %d\n", (*h)[0])
for h.Len() > 0 {
fmt.Printf("%d ", heap.Pop(h))
}
}

▹ Example (PriorityQueue)

▾ Example (PriorityQueue)

This example creates a PriorityQueue with some items, adds and manipulates an item,
and then removes the items in priority order.

Code:

package heap_test
import (
"container/heap"
"fmt"
)
type Item struct {
value string
priority int
index int
}
type PriorityQueue []*Item
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
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
*pq = old[0 : n-1]
return item
}
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
item.value = value
item.priority = priority
heap.Fix(pq, item.index)
}
func Example_priorityQueue() {
items := map[string]int{
"banana": 3, "apple": 2, "pear": 4,
}
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)
item := &Item{
value: "orange",
priority: 1,
}
heap.Push(&pq, item)
pq.update(item, item.value, 5)
for pq.Len() > 0 {
item := heap.Pop(&pq).(*Item)
fmt.Printf("%.2d:%s ", item.priority, item.value)
}
}

In the call graph viewer below, each node
is a function belonging to this package
and its children are the functions it
calls—perhaps dynamically.

The root nodes are the entry points of the
package: functions that may be called from
outside the package.
There may be non-exported or anonymous
functions among them if they are called
dynamically from another package.

Click a node to visit that function's source code.
From there you can visit its callers by
clicking its declaring `func`

token.

Functions may be omitted if they were
determined to be unreachable in the
particular programs or tests that were
analyzed.

func Fix(h Interface, i int)

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 Init(h Interface)

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 Pop(h Interface) interface{}

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 Push(h Interface, x interface{})

Push pushes the element x onto the heap. The complexity is
O(log(n)) where n = h.Len().

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

Remove removes the element at index i from the heap.
The complexity is O(log(n)) where n = h.Len().

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(x interface{})
Pop() interface{}
}