Documentation
¶
Overview ¶
Package binaryheap implements a binary heap which is a binary 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 a container.Less method on T, so Heap.Push adds items while Heap.Pop removes the highest-priority item from queue.
The Less method on T defines this heap as either min or max heap.
Reference: http://en.wikipedia.org/wiki/Binary_heap
Index ¶
- type Heap
- func (h *Heap[T]) Clear()
- func (h *Heap[T]) Elements() []T
- func (h *Heap[T]) Fix(i int)
- func (h *Heap[T]) Len() int
- func (h *Heap[T]) MarshalJSON() ([]byte, error)
- func (h *Heap[T]) Peek() (value T, ok bool)
- func (h *Heap[T]) Pop() (value T, ok bool)
- func (h *Heap[T]) Push(v T)
- func (h *Heap[T]) Remove(i int) (value T, ok bool)
- func (h *Heap[T]) String() string
- func (h *Heap[T]) UnmarshalJSON(data []byte) error
- func (h *Heap[T]) Update(i int, v T)
- func (h *Heap[T]) Values() []T
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Heap ¶
type Heap[T any] struct { // contains filtered or unexported fields }
Heap represents an binary heap which holds the elements in a slice.
func New ¶
New returns an initialized heap with cmp.Less as the less function and the given values v added.
func NewFunc ¶
NewFunc returns an initialized heap with the given function less as the less function and the given values v added.
func (*Heap[T]) Elements ¶
func (h *Heap[T]) Elements() []T
Elements returns the underlying elements slice of heap. Note: Do not change the index of any element because index must be maintained by the heap. You can update any element value, and call Heap.Fix with the index of the element to update. Or you can just call Heap.Update with the index of the element to update and the new value to update to. At the same time, you can also remove any element by call Heap.Remove with the index of the element to remove.
func (*Heap[T]) Fix ¶
Fix re-establishes queue 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 Heap.Remove followed by a Heap.Push of the new value. The complexity is O(log n) where n = h.Len().
func (*Heap[T]) MarshalJSON ¶
MarshalJSON marshals heap into valid JSON. Ref: std json.Marshaler.
func (*Heap[T]) Peek ¶
Peek returns the top element if exists in heap without removing it. The ok result indicates whether such element was found in heap.
func (*Heap[T]) Pop ¶
Pop removes the top element if exists in heap and returns it. The ok result indicates whether such element was removed from heap.
func (*Heap[T]) Push ¶
func (h *Heap[T]) Push(v T)
Push adds the given value v to heap.
Example ¶
package main
import (
"fmt"
"github.com/docodex/gopkg/container/tree/binaryheap"
)
func main() {
h := binaryheap.New(2, 1, 5)
h.Push(3)
v, _ := h.Peek()
fmt.Printf("minimum: %d\n", v)
for h.Len() > 0 {
v, _ := h.Pop()
fmt.Printf("%d ", v)
}
}
Output: minimum: 1 1 2 3 5
func (*Heap[T]) Remove ¶
Remove removes and returns the element at the given index i from heap. The complexity is O(log n) where n = h.Len().
func (*Heap[T]) UnmarshalJSON ¶
UnmarshalJSON unmarshals a JSON description of heap. The input can be assumed to be a valid encoding of a JSON value. UnmarshalJSON must copy the JSON data if it wishes to retain the data after returning. Ref: std json.Unmarshaler.
func (*Heap[T]) Update ¶
Update updates the element value to v at index i, and re-establishes heap ordering. Heap.Update is a shortcut for update an element value at the given index i with the given value v followed by a Heap.Fix with the given index i. It is equivalent to, but less expensive than, calling Heap.Remove with the given index i followed by a Heap.Push of the given value v. The complexity is O(log n) where n = h.Len().
Example ¶
package main
import (
"fmt"
"github.com/docodex/gopkg/container/tree/binaryheap"
)
func main() {
// Some items and their priorities.
items := map[string]int{
"banana": 3, "apple": 2, "pear": 4,
}
// An Item is something we manage in a priority queue.
type Item struct {
value string // The value of the item.
priority int // The priority of the item in queue.
}
// Create a priority queue, put the items in it, and
// establish the priority queue (heap) invariants.
pq := make([]*Item, 0, len(items))
for value, priority := range items {
pq = append(pq, &Item{
value: value,
priority: priority,
})
}
h := binaryheap.NewFunc(func(a, b *Item) bool {
// We want Pop to give us the highest, not lowest, priority so we use greater than here.
return a.priority > b.priority
}, pq...)
// Insert a new item and then modify its priority.
h.Push(&Item{
value: "orange",
priority: 5,
})
item, _ := h.Peek()
h.Update(0, &Item{
value: item.value,
priority: 1,
})
// Take the items out; they arrive in decreasing priority order.
for h.Len() > 0 {
item, _ := h.Pop()
fmt.Printf("%.2d:%s ", item.priority, item.value)
}
}
Output: 04:pear 03:banana 02:apple 01:orange
Source Files