Reference implementations of heap data structures in Go
$ go get -u github.com/theodesp/go-heaps
Heaps
- Pairing Heap: A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance,
package main
import (
pairingHeap "go-heaps/pairing"
"fmt"
)
func main() {
heap := pairingHeap.NewWithIntComparator()
heap.Insert(4)
heap.Insert(3)
heap.Insert(2)
heap.Insert(5)
fmt.Println(heap.DeleteMin()) // 2
fmt.Println(heap.DeleteMin()) // 3
fmt.Println(heap.DeleteMin()) // 4
fmt.Println(heap.DeleteMin()) // 5
}
Operation | Pairing |
---|---|
FindMin | Θ(1) |
DeleteMin | O(log n) |
Insert | Θ(1) |
Find | O(n) |
Delete | O(log n) |
Adjust | O(log n) |
Copyright © 2017 Theo Despoudis MIT license