README
¶
minmaxheap
Min-max heap operations for any type that implements heap.Interface. A min-max heap can be used to implement a double-ended priority queue.
Min-max heap implementation from the 1986 paper "Min-Max Heaps and Generalized Priority Queues" by Atkinson et. al. https://doi.org/10.1145/6617.6621.
| Operation | min-max heap | heap |
|---|---|---|
| Init | O(n) | O(n) |
| Push | O(log n) | O(log n) |
| Pop | O(log n) | O(log n) |
| PopMax | O(log n) | O(n) |
| Fix | O(log n) | O(log n) |
Documentation
¶
Overview ¶
Package minmaxheap provides min-max heap operations for any type that implements heap.Interface. A min-max heap can be used to implement a double-ended priority queue.
Min-max heap implementation from the 1986 paper "Min-Max Heaps and Generalized Priority Queues" by Atkinson et. al. https://doi.org/10.1145/6617.6621.
Example ¶
package main
import (
"fmt"
heap "github.com/esote/minmaxheap"
)
// IntHeap is a min-heap of ints.
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func main() {
h := &IntHeap{2, 1, 5}
heap.Init(h)
heap.Push(h, 3)
fmt.Println("min:", heap.Pop(h))
fmt.Println("max:", heap.PopMax(h))
}
Output: min: 1 max: 5
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Fix ¶
Fix re-establishes the heap ordering after the element at index i has changed its value. Changing the value of the element at index i and then calling Fix is equivalent to, but less expensive than, calling Remove(h, i) followed by a Push of the new value. The complexity is O(log n) where n = h.Len().
func Init ¶
func Init(h Interface)
Init establishes the heap invariants required by the other routines in this package. Init may be called whenever the heap invariants may have been invalidated. The complexity is O(n) where n = h.Len().
func Pop ¶
func Pop(h Interface) interface{}
Pop removes and returns the minimum element (according to Less) from the heap. The complexity is O(log n) where n = h.Len().
func PopMax ¶
func PopMax(h Interface) interface{}
PopMax removes and returns the maximum element (according to Less) from the heap. The complexity is O(log n) where n = h.Len().
Source Files