## package heap

`import "github.com/ncw/gotemplate/heap"`

Package heap provides heap operations for a type A and a comparison
function Less. 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.

This provides a min-heap with the following invariants (established
after Init has been called or if the data is empty or sorted):

!Less(h[j], h[i]) for 0 <= i < len(h) and j = 2*i+1 or 2*i+2 and j < len(h)

A heap is a common way to implement a priority queue. To build a
priority queue, use 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.

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

Code:

h := &heap.Heap{2, 1, 5}
h.Init()
h.Push(3)
fmt.Printf("minimum: %d\n", (*h)[0])
for len(*h) > 0 {
fmt.Printf("%d ", h.Pop())
}

Output:

minimum: 1
1 2 3 5

#### Examples ¶

heap.go

Less is a function to compare two As

An A is the element in the slice []A we are keeping as a heap

template type Heap(A, Less)

Heap stored in an slice

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 h.Remove(i) followed by a Push of the new value.
The complexity is O(log(n)) where n = len(h).

Init is compulsory 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 = len(h).

Pop removes the minimum element (according to Less) from the heap
and returns it. The complexity is O(log(n)) where n = len(h).
It is equivalent to h.Remove(0).

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

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

Updated 2017-05-11.
Refresh now.
Tools for package owners.
This is an inactive package (no imports and no commits in at least two years).