Documentation
¶
Overview ¶
Package heap contains the implementation of a generic heap derived from the standard container/heap package. Additionally, this package provides some convenince implementations that operate using go slices, simplifying the interface requirements.
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 interface.
package main
import (
"fmt"
"github.com/segmentio/datastructures/v2/container/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
}
func (i *Item) SetIndex(index int) {
i.index = 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(heap.IndexHeap[*Item], 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)
// Update the priority and fix the index
item.priority = 5
heap.Fix(&pq, item.index)
// Take the items out; they arrive in decreasing priority order.
for pq.Len() > 0 {
item := heap.Pop(&pq)
fmt.Printf("%.2d:%s ", item.priority, item.value)
}
}
Output: 05:orange 04:pear 03:banana 02:apple
Index ¶
Examples ¶
Constants ¶
const NoIndex = -1
Variables ¶
This section is empty.
Functions ¶
func 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 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 Pop ¶
Pop removes and returns the minimum element (according to Less) from the heap. The complexity is O(log n) where n = h.Len(). Pop is equivalent to Remove(h, 0).
Types ¶
type Entry ¶
type Entry[T any] interface { // Less reports whether the receiver is less than the passed-in value. // // This must hold the same transitivity of the Less method in [sort.Interface]. Less(T) bool }
Entry defines the interface requirement for each entry in a heap.Heap.
type Heap ¶
type Heap[T Entry[T]] []T
Heap provides a convenience for implementing the heap.Interface as a slice with entries of type T.
func (Heap[T]) Len ¶
Len returns the number of items in the heap. This implements the Len method of heap.Interface.
func (*Heap[T]) Pop ¶
func (h *Heap[T]) Pop() T
Pop implements heap.Interface. This method should not be called directly,w use heap.Pop instead.
func (*Heap[T]) Push ¶
func (h *Heap[T]) Push(x T)
Push implements heap.Interface. This method should not be called directly, use heap.Push instead.
func (Heap[T]) Swap ¶
Swap implements heap.Interface. This method should not be called directly.
type IndexEntry ¶
type IndexEntry[T any] interface { Entry[T] // SetIndex updates the entry's index position within the heap slice. SetIndex(int) }
IndexEntry defines the interface requirement for each entry in a heap.IndexHeap.
type IndexHeap ¶
type IndexHeap[T IndexEntry[T]] []T
IndexHeap provides a convenience for implementing the heap.Interface as a slice with entries of type T that also track the index position within each entry. By storing the index, entries can easily be updated with heap.Fix and removed using heap.Remove.
func (IndexHeap[T]) Len ¶
Len returns the number of items in the heap. This implements the Len method of heap.Interface.
func (IndexHeap[T]) Less ¶
Less implements heap.Interface.
func (*IndexHeap[T]) Pop ¶
func (h *IndexHeap[T]) Pop() T
Pop implements heap.Interface. This method should not be called directly, use heap.Pop instead.
func (*IndexHeap[T]) Push ¶
func (h *IndexHeap[T]) Push(x T)
Push implements heap.Interface. This method should not be called directly, use heap.Push instead.
func (IndexHeap[T]) Swap ¶
Swap implements heap.Interface. This method should not be called directly.
type Interface ¶
The Interface type describes the requirements for a type using the routines in this package. Any type that implements it 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.
Source Files