heap.Init, heap.Push, and heap.Pop
type Interface interface {
sort.Interface
Push(x any) // add x as element Len()
Pop() any // remove and return element Len() - 1.
}
func Init(h Interface)
func Push(h Interface, x any)
func Pop(h Interface) anyImplement Push and Pop at the tail. Call heap.Push and heap.Pop to maintain the heap. Calling the methods directly can violate the invariants.
| Parameter | Description |
|---|---|
h | A pointer to a type that implements heap.Interface. Examples use *intHeap so Push and Pop can resize the slice. |
x | The element passed to heap.Push. The interface Push method should append it as the new last element. |
Returns: heap.Pop returns the minimum element according to Less, after restoring the heap. The broken path in this example is only to show a violated invariant; it is not a usage pattern.
- The first line is the correct sequence: 1 3 4 5. The second line starts with 3 because 1 was appended without heap.Push.
- Equal priorities are not demonstrated here, and no pop order is promised for items that Less treats as equal.
package main
import (
"container/heap"
"fmt"
)
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 any) { *h = append(*h, x.(int)) }
func (h *intHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
func main() {
h := intHeap{5, 3, 4}
heap.Init(&h)
heap.Push(&h, 1)
fmt.Println(heap.Pop(&h), heap.Pop(&h), heap.Pop(&h), heap.Pop(&h))
broken := intHeap{5, 3, 4}
heap.Init(&broken)
broken.Push(1) // appends at the tail without restoring the heap
fmt.Println(heap.Pop(&broken), heap.Pop(&broken), heap.Pop(&broken), heap.Pop(&broken))
}Expected output
1 3 4 5
3 1 4 5
Related: sort.Interface, cmp.Less, Official container/heap