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

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