Documentation ¶
Overview ¶
Package heaps provides a heap implementation for any type.
Example ¶
package main import ( "fmt" "github.com/houz42/abstract/heaps" ) func main() { h := heaps.New(2, 1, 5, 6) h.Push(3) h.Remove(3) fmt.Printf("minimum: %d\n", h.Top()) for h.Len() > 0 { fmt.Printf("%d ", h.Pop()) } }
Output: minimum: 1 1 2 3 5
Example (PriorityQueue) ¶
package main import ( "fmt" "github.com/houz42/abstract/heaps" ) func main() { type process struct { pid int niceness int } queue := heaps.NewFunc[process](func(x, y process) bool { return x.niceness < y.niceness }) queue.Push(process{pid: 1, niceness: -20}) queue.Push(process{pid: 2, niceness: 0}) queue.Push(process{pid: 3, niceness: 10}) queue.Push(process{pid: 4, niceness: -1}) for queue.Len() > 0 { p := queue.Pop() fmt.Printf("start process %d with niceness %d\n", p.pid, p.niceness) } }
Output: start process 1 with niceness -20 start process 4 with niceness -1 start process 2 with niceness 0 start process 3 with niceness 10
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 { // contains filtered or unexported fields }
Heap is a tree with the property that each node is the minimum-valued (or maximum if reversed) node in its subtree. The minimum (maximum) element in the tree is the root, at index 0.
A newly created Heap is a min-heap. If a max-heap is wanted, call [Reverse] on it.
A heap is a common way to implement a priority queue. To build a priority queue, pass in a less method which orders the elements by their priorities, so [Push] adds items while [Pop] removes the highest-priority item from the queue. See the example for more details.
A Heap is not safe for concurrent use by multiple goroutines.
func (*Heap[E]) Pop ¶
func (h *Heap[E]) Pop() E
Pop removes and returns the first element from the heap. The complexity is O(log n) where n = h.Len(). Pop is equivalent to [Remove](h).
func (*Heap[E]) Push ¶
Push pushes the element x onto the heap. The complexity is O(log n) where n = h.Len().
func (*Heap[E]) Remove ¶
Remove removes and returns the element at index i from the heap. The complexity is O(log n) where n = h.Len().
Example ¶
package main import ( "fmt" "github.com/houz42/abstract/heaps" ) func main() { h := heaps.New(1, 5, 3, 2) fmt.Println("removed:", h.Remove(2)) for h.Len() > 0 { fmt.Println(h.Pop()) } }
Output: removed: 3 1 2 5
func (*Heap[E]) Reverse ¶
Reverse returns a new Heap in which the elements will be pop out in reserved sequence to the original one. That is, if h is a min-heap, a max-heap will be returned, or vice versa.
Example ¶
package main import ( "fmt" "github.com/houz42/abstract/heaps" ) func main() { type plan struct { name string severity int } queue := heaps.NewFunc[plan](func(x, y plan) bool { return x.severity < y.severity }).Reverse() queue.Push(plan{name: "call friend", severity: 1}) queue.Push(plan{name: "finish report", severity: 3}) queue.Push(plan{name: "buy food", severity: 2}) for queue.Len() > 0 { plan := queue.Pop() fmt.Printf("%d: %s\n", plan.severity, plan.name) } }
Output: 3: finish report 2: buy food 1: call friend