README
¶
Heaps
Documentation
¶
Overview ¶
Package heap provides min-heap data structures.
Example (Changed) ¶
package main
import (
"fmt"
"github.com/jba/heap"
)
func main() {
type intWithIndex struct {
value int
index int
}
h := heap.NewFunc(func(a, b *intWithIndex) int {
return a.value - b.value
})
h.SetIndexFunc(func(v *intWithIndex) *int { return &v.index })
item1 := &intWithIndex{value: 5}
item2 := &intWithIndex{value: 3}
item3 := &intWithIndex{value: 7}
h.InsertSlice([]*intWithIndex{item1, item2, item3})
// Get the current min.
fmt.Println(h.Min().value)
// Modify item1's value (currently 5, make it smaller).
item1.value = 1
// Call Changed to restore heap invariant.
h.Changed(item1)
// Now item1 should be the new minimum.
fmt.Println(h.Min().value)
}
Output: 3 1
Example (Delete) ¶
package main
import (
"fmt"
"github.com/jba/heap"
)
func main() {
type intWithIndex struct {
value int
index int
}
h := heap.NewFunc(func(a, b *intWithIndex) int {
return a.value - b.value
})
h.SetIndexFunc(func(v *intWithIndex) *int { return &v.index })
item1 := &intWithIndex{value: 5}
item2 := &intWithIndex{value: 3}
item3 := &intWithIndex{value: 7}
item4 := &intWithIndex{value: 1}
h.InsertSlice([]*intWithIndex{item1, item2, item3, item4})
// Delete specific items.
h.Delete(item1)
h.Delete(item2)
// Remaining elements.
for v := range h.Drain() {
fmt.Println(v.value)
}
}
Output: 1 7
Example (KSmallest) ¶
Example_kSmallest demonstrates finding the K smallest elements using a max-heap and ChangeMin.
package main
import (
"fmt"
"github.com/jba/heap"
)
func main() {
// To find the K smallest elements, use a max-heap of size K.
// The heap's "min" (actually max) is the largest of the K smallest seen so far.
h := heap.NewFunc(func(a, b int) int {
return b - a // Reverse comparison for max-heap.
})
data := []int{7, 2, 9, 1, 5, 8, 3, 6, 4, 10}
k := 3
// Insert first K elements.
h.InsertSlice(data[:k])
// For remaining elements, replace the max if we find a smaller value.
for _, v := range data[k:] {
if v < h.Min() {
h.ChangeMin(v)
}
}
// Drain the heap to get the K smallest (in descending order).
fmt.Println("3 smallest elements:")
for v := range h.Drain() {
fmt.Println(v)
}
}
Output: 3 smallest elements: 3 2 1
Example (MaxHeap) ¶
package main
import (
"fmt"
"github.com/jba/heap"
)
func main() {
// Create a max-heap using a custom comparison function.
h := heap.NewFunc(func(a, b int) int {
// Reverse the comparison for max-heap.
return b - a
})
h.InsertSlice([]int{5, 3, 7, 1})
// Extract maximum values.
fmt.Println(h.TakeMin()) // "Min" extracts the element that compares smallest
fmt.Println(h.TakeMin())
}
Output: 7 5
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Heap ¶
type Heap[T any] interface { // Insert adds an element to the heap, preserving the heap property. Insert(value T) // InsertSlice adds all elements of s to the heap, then re-establishes // the heap property. // The caller must not subsequently modify s. InsertSlice(s []T) // Min returns the minimum element in the heap without removing it. // It panics if the heap is empty. Min() T // TakeMin removes and returns the minimum element from the heap. // It panics if the heap is empty. TakeMin() T // ChangeMin replaces the minimum value in the heap with the given value. // It panics if the heap is empty. ChangeMin(v T) // Len returns the number of elements in the heap. Len() int // All returns an iterator over all elements in the heap // in unspecified order. All() iter.Seq[T] // Drain removes and returns the heap elements in sorted order, // from smallest to largest. // // The result is undefined if the heap is changed during iteration. Drain() iter.Seq[T] // Clear removes all elements from the heap. Clear() // SetIndexFunc sets a function that returns a pointer index for // the given heap element. The index function must not return nil. // // SetIndexFunc enables the use of the Delete and Changed methods. // It must be called initially, before any other method is called. SetIndexFunc(f func(T) *int) // Changed restores the heap invariant after the item's value // has been changed. Call this method after modifying the value // of the item. If the item has been deleted or the heap has been // cleared, Changed does nothing. // // The Heap must have an index function. Changed(v T) // Delete removes the item with the given index from the heap. // If the item has already been deleted or the heap has been cleared, // Delete does nothing. // // The Heap must have an index function. Delete(v T) }
A Heap is a binary min-heap.
Example ¶
package main
import (
"cmp"
"fmt"
"github.com/jba/heap"
)
func main() {
h := heap.NewFunc[int](cmp.Compare[int])
// Insert elements.
h.InsertSlice([]int{5, 3, 7, 1})
// Extract elements in sorted order.
fmt.Println(h.TakeMin())
fmt.Println(h.TakeMin())
fmt.Println(h.TakeMin())
fmt.Println(h.TakeMin())
}
Output: 1 3 5 7
Source Files
Directories
Click to show internal directories.
Click to hide internal directories.