Skip to content

Reference implementations of heap data structures in Go - treap, skew, leftlist, pairing, fibonacci

License

Notifications You must be signed in to change notification settings

theodesp/go-heaps

Repository files navigation

go-heaps All Contributors

GoDoc License

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
Miroojin Bakshi

💻
Syfaro
Syfaro

💻
Theofanis Despoudis
Theofanis Despoudis

💻
Radliński Ignacy
Radliński Ignacy

💻
Don McNamara
Don McNamara

🚇
Afrizal Fikri
Afrizal Fikri

💻
Logan HAUSPIE
Logan HAUSPIE

💻
Song Guo
Song Guo

💻
Safwan Mohammed
Safwan Mohammed

⚠️ 💻

This project follows the all-contributors specification. Contributions of any kind welcome!

LICENCE

Copyright © 2017 Theo Despoudis MIT license

About

Reference implementations of heap data structures in Go - treap, skew, leftlist, pairing, fibonacci

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published