Documentation
¶
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Heap ¶
type Heap[T any] struct { Limit int // Maximum number of entries to keep (0 = unlimited). Optional. Less func(a, b T) bool // Less returns true if a < b. Required. // contains filtered or unexported fields }
Heap implements a heap of T. If Limit is specified, only the greatest elements (according to Less) up to Limit are kept.
When removing elements, the smallest element (according to Less) is returned first. If using Heap as a max-heap, these elements need to stored in reverse order.
Example (Greatest) ¶
ExampleHeap_greatest shows how to use a topk.Heap to get the top-k greatest elements in descending order.
package main
import (
"fmt"
"slices"
"github.com/grafana/loki/v3/pkg/util/topk"
)
func main() {
heap := &topk.Heap[int]{
Limit: 3,
Less: func(a, b int) bool { return a < b },
}
for i := range 10 {
heap.Push(i)
}
actual := heap.PopAll()
slices.Reverse(actual) // Reverse to get in greatest-descending order.
fmt.Println(actual)
}
Output: [9 8 7]
Example (Least) ¶
ExampleHeap_least shows how to use a topk.Heap to get the top-k least elements in ascending order.
package main
import (
"fmt"
"slices"
"github.com/grafana/loki/v3/pkg/util/topk"
)
func main() {
heap := &topk.Heap[int]{
Limit: 3,
Less: func(a, b int) bool { return a > b },
}
for i := range 10 {
heap.Push(i)
}
actual := heap.PopAll()
slices.Reverse(actual) // Reverse to get in least-ascending order.
fmt.Println(actual)
}
Output: [0 1 2]
func (*Heap[T]) Peek ¶ added in v3.7.0
Peek returns the minimum element from the heap without removing it. Peek returns the zero value for T and false if the heap is empty.
func (*Heap[T]) Pop ¶
Pop removes and returns the minimum element from the heap. Pop returns the zero value for T and false if the heap is empty.
func (*Heap[T]) PopAll ¶
func (h *Heap[T]) PopAll() []T
PopAll removes and returns all elements from the heap in sorted order.
func (*Heap[T]) Push ¶
func (h *Heap[T]) Push(v T) (res PushResult, prev T)
Push adds v into the heap. If the heap is full, v is added only if it is larger than the smallest value in the heap.
Push returns the result of the operation:
- PushResultNone if h is full and v is too small to be added, - PushResultPushed if h wasn't full and v was added, or - PushResultReplaced if h was full and v replaced the smallest value.
If Push returns PushResultReplaced, the previous smallest value is returned in prev. Otherwise, prev is the zero value for T.
type PushResult ¶
type PushResult int
PushResult describes the result of a Heap.Push operation.
const ( PushResultNone PushResult = iota // PushResultNone indicates that the heap was unchanged. PushResultPushed // PushResultPushed indicates that a value was added without removing existing values. PushResultReplaced // PushResultReplaced indicates that the smallest value was replaced with a new value. )
Source Files