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