go_heaps

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
• type Extended
• type Integer
  • func (a Integer) Compare(b Item) int
• type Interface
• type Item
• type ItemIterator
• type String
  • func (a String) Compare(b Item) int

Constants

const Version = "0.0.1"

Version The main version number that is being run at the moment.

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 Integer

type Integer int

Integer implements the Item interface

func (Integer) Compare

func (a Integer) Compare(b Item) int

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

type ItemIterator func(item Item) bool

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.

type String

type String string

String implements the Item interface

func (String) Compare

func (a String) Compare(b Item) int