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
Source Files