Documentation
¶
Overview ¶
Package heap provides heap operations on a slice of values. 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.
package main
import (
"fmt"
"github.com/rogpeppe/generic/heap"
)
func main() {
h := heap.New([]int{2, 1, 5}, func(a, b int) bool {
return a < b
}, nil)
h.Push(3)
fmt.Printf("minimum: %d\n", h.Items[0])
for h.Len() > 0 {
fmt.Printf("%d ", h.Pop())
}
}
Output: minimum: 1 1 2 3 5
Example (PriorityQueue) ¶
This example creates a PriorityQueue with some items, adds and manipulates an item, and then removes the items in priority order.
// This example demonstrates a priority queue built using the Heap type.
package main
import (
"fmt"
"github.com/rogpeppe/generic/heap"
)
// 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.
}
func (i *Item) less(j *Item) bool {
// We want Pop to give us the highest, not lowest, priority so we use greater than here.
return i.priority > j.priority
}
// 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.
itemsMap := 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.
items := make([]*Item, len(itemsMap))
i := 0
for value, priority := range itemsMap {
items[i] = &Item{
value: value,
priority: priority,
index: i,
}
i++
}
pq := heap.New(items, (*Item).less, func(i **Item, index int) {
(*i).index = index
})
// Insert a new item and then modify its priority.
item := &Item{
value: "orange",
priority: 1,
}
pq.Push(item)
item.priority = 5
pq.Fix(item.index)
// Take the items out; they arrive in decreasing priority order.
for pq.Len() > 0 {
item := pq.Pop()
fmt.Printf("%.2d:%s ", item.priority, item.value)
}
}
Output: 05:orange 04:pear 03:banana 02:apple
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Heap ¶
type Heap[E any] struct { // Items holds all the items in the heap. The first item is less // than all the others. Items []E // contains filtered or unexported fields }
Heap implements a binary heap.
func New ¶
New returns a binary heap on the items slice, using less to compare. If setIndex is non-nil, it will be called when an item in the heap is moved, and passed a pointer to the item that has moved and its new index in the slice.
func (*Heap[E]) 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 (*Heap[E]) Init ¶
func (h *Heap[E]) Init()
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 (*Heap[E]) Pop ¶
func (h *Heap[E]) Pop() E
Pop removes and returns the minimum element (according to the less function) from the heap. The complexity is O(log n) where n = h.Len(). Pop is equivalent to Remove(h, 0).
Source Files