README
¶
go-heaps
Reference implementations of heap data structures in Go
Installation
$ go get -u github.com/theodesp/go-heaps
Contents
Heaps
- Pairing Heap: A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance.
- Leftist Heap: a variant of a binary heap. Every node has an s-value which is the distance to the nearest leaf. In contrast to a binary heap, a leftist tree attempts to be very unbalanced.
- Skew Heap: A skew heap (or self-adjusting heap) is a heap data structure implemented as a binary tree. Skew heaps are advantageous because of their ability to merge more quickly than binary heaps.
- Fibonacci Heap: a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better amortized running time than many other priority queue data structures including the binary heap and binomial heap.
- Binomial Heap: A Binomial Heap is a collection of Binomial Trees. A Binomial Heap is a set of Binomial Trees where each Binomial Tree follows Min Heap property. And there can be at most one Binomial Tree of any degree.
- Treap Heap: A Treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys.
- Rank Pairing Heap: A heap (priority queue) implementation that combines the asymptotic efficiency of Fibonacci heaps with much of the simplicity of pairing heaps
Usage
package main
import (
"github.com/theodesp/go-heaps"
pairingHeap "github.com/theodesp/go-heaps/pairing"
"fmt"
)
func main() {
heap := pairingHeap.New()
heap.Insert(go_heaps.Integer(4))
heap.Insert(go_heaps.Integer(3))
heap.Insert(go_heaps.Integer(2))
heap.Insert(go_heaps.Integer(5))
fmt.Println(heap.DeleteMin()) // 2
fmt.Println(heap.DeleteMin()) // 3
fmt.Println(heap.DeleteMin()) // 4
fmt.Println(heap.DeleteMin()) // 5
}
Complexity
| Operation | Pairing | Leftist | Skew | Fibonacci | Binomial | Treap |
|---|---|---|---|---|---|---|
| FindMin | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(log n) | O(n) |
| DeleteMin | O(log n) | O(log n) | O(log n) | O(log n) | Θ(log n) | O(n) |
| Insert | Θ(1) | O(log n) | O(log n) | Θ(1) | Θ(1) | O(n) |
| Find | O(n) | |||||
| Delete | O(n) | O(log n) | O(n) | Θ(log n) | O(n) | |
| Adjust | O(n) | O(log n) | O(n) | Θ(log n) | O(n) | |
| Meld | Θ(1) |
| Operation | Rank Pairing |
|---|---|
| FindMin | Θ(1) |
| DeleteMin | O(log n) |
| Insert | Θ(1) |
| Find | O(n) |
| Delete | O(n) |
| Adjust | O(n) |
| Meld | Θ(1) |
Contributors
Thanks goes to these wonderful people (emoji key):
 Miroojin Bakshi 💻 |  Syfaro 💻 |  Theofanis Despoudis 💻 |  Radliński Ignacy 💻 |  Don McNamara 🚇 |  Afrizal Fikri 💻 |  Logan HAUSPIE 💻 |
 Song Guo 💻 |  Safwan Mohammed ⚠️ 💻 |
This project follows the all-contributors specification. Contributions of any kind welcome!
LICENCE
Copyright © 2017 Theo Despoudis MIT license
Documentation
¶
Index ¶
Constants ¶
View Source
const Version = "0.0.1"
Version The main version number that is being run at the moment.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Extended ¶
type Extended interface {
Interface
// Return the heap formed by taking the union of the item disjoint
// current heap and a
Meld(a Interface) Interface
// Adjusts the key of item old in heap h to new
Adjust(old, new Item) Item
// Delete arbitrary item from heap h.
Delete(item Item) Item
}
Extended adds operations on heaps are often useful.
type Interface ¶
type Interface interface {
// Inserts an element to the heap and returns it
Insert(v Item) Item
// DeleteMin deletes and returns the smallest element
DeleteMin() Item
// FindMin returns the minimum element
FindMin() Item
// Removes all items
Clear()
}
Interface is basic interface that all Heaps implement.
type Item ¶
type Item interface {
// Should return a number:
// negative , if a < b
// zero , if a == b
// positive , if a > b
Compare(than Item) int
}
Item is the basic element that is inserted in a heap
type ItemIterator ¶
ItemIterator allows callers of Do to iterate in-order over portions of the tree. When this function returns false, iteration will stop and the function will immediately return.
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
Package binomial implements a Binomial heap Data structure Structure is not thread safe.
|
Package binomial implements a Binomial heap Data structure Structure is not thread safe. |
|
example
|
|
|
leftist
command
|
|
|
pairing
command
|
|
|
rank_pairing
command
|
|
|
skew
command
|
|
|
treap
command
|
|
|
Package fibonacci implements a Fibonacci FibonacciHeap Data structure Reference: https://en.wikipedia.org/wiki/Fibonacci_heap Implementation from Introduction to Algorithms by T. Cormen
|
Package fibonacci implements a Fibonacci FibonacciHeap Data structure Reference: https://en.wikipedia.org/wiki/Fibonacci_heap Implementation from Introduction to Algorithms by T. Cormen |
|
Package pairing implements a Pairing heap Data structure Structure is not thread safe.
|
Package pairing implements a Pairing heap Data structure Structure is not thread safe. |
|
Package skew implements a Skew heap Data structure Structure is not thread safe.
|
Package skew implements a Skew heap Data structure Structure is not thread safe. |
Click to show internal directories.
Click to hide internal directories.