README
¶
heap
A generic, type-safe heap (priority queue) for Go.
Wraps container/heap with generics so you never have to write another heap.Interface implementation.
Install
go get github.com/frizzkitten/heap
Usage
Min-heap
h := heap.NewMin([]int{3, 1, 2}, func(v int) int { return v })
value, ok := h.Pop() // 1, true
value, ok = h.Pop() // 2, true
value, ok = h.Pop() // 3, true
value, ok = h.Pop() // 0, false (empty)
Max-heap with custom types
type Job struct {
Name string
Priority int
}
jobs := []Job{
{Name: "low", Priority: 1},
{Name: "high", Priority: 10},
{Name: "medium", Priority: 5},
}
getPriority := func(j Job) int { return j.Priority }
h := heap.NewMax(jobs, getPriority)
value, ok := h.Pop() // {high 10}, true
value, ok = h.Pop() // {medium 5}, true
value, ok = h.Pop() // {low 1}, true
Starting empty
h := heap.NewMin(nil, func(v int) int { return v })
h.Push(5)
h.Push(2)
h.Push(8)
value, ok := h.Pop() // 2, true
API
| Method | Description | Time complexity |
|---|---|---|
NewMin(startingValues, getPriority) |
Create a min-heap | O(n) |
NewMax(startingValues, getPriority) |
Create a max-heap | O(n) |
Push(value) |
Add an element | O(log n) |
Pop() |
Remove and return the highest-priority element | O(log n) |
Peek() |
Return the highest-priority element without removing it | O(1) |
Length() |
Return the number of elements | O(1) |
Note
startingValues is reordered in place during heap construction. If you need to preserve the original order, pass a copy.
License
Documentation
¶
Overview ¶
Package heap provides a generic, type-safe priority queue backed by container/heap. It supports both min-heaps and max-heaps with a user-defined priority function.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Heap ¶
Heap is a generic priority queue. T is the element type and S is the priority type used for ordering.
func NewMax ¶
NewMax creates a max-heap where the highest priority value is popped first. startingValues will be reordered in place; pass nil to start empty. Runs in O(n) time where n is len(startingValues).
Example ¶
package main
import (
"fmt"
"github.com/frizzkitten/heap"
)
func main() {
type Job struct {
Name string
Priority int
}
jobs := []Job{
{Name: "low", Priority: 1},
{Name: "high", Priority: 10},
{Name: "medium", Priority: 5},
}
getPriority := func(j Job) int { return j.Priority }
h := heap.NewMax(jobs, getPriority)
value, ok := h.Pop()
fmt.Println(value.Name, ok)
value, ok = h.Pop()
fmt.Println(value.Name, ok)
value, ok = h.Pop()
fmt.Println(value.Name, ok)
value, ok = h.Pop()
fmt.Println(value.Name, ok)
}
Output: high true medium true low true false
func NewMin ¶
NewMin creates a min-heap where the lowest priority value is popped first. startingValues will be reordered in place; pass nil to start empty. Runs in O(n) time where n is len(startingValues).
Example ¶
package main
import (
"fmt"
"github.com/frizzkitten/heap"
)
func main() {
h := heap.NewMin([]int{3, 1, 2}, func(v int) int { return v })
fmt.Println(h.Pop())
fmt.Println(h.Pop())
fmt.Println(h.Pop())
fmt.Println(h.Pop())
}
Output: 1 true 2 true 3 true 0 false
func (*Heap[T, S]) Peek ¶ added in v0.2.0
Peek returns the highest-priority element without removing it. Returns false if the heap is empty. Runs in O(1) time.
Source Files