mmheap

README

go-mmheap

Package mmheap provides a drop-in min-max heap for any type that implements heap.Interface.

In a min-max heap, the minimum element is at the root at index 0, and the maximum element is in one of the two root children.

Thus, a min-max heap provides an efficient way to access either the minimum or maximum elements in a set in O(1) time.

Due to the increased number of comparisons to implement a min-heap, its runtime is slower than a general heap (in this implementation, just under 2x). Because of this, unless you need to continually access both the minimum and maximum elements, it may be beneficial to use a different data structure. Even if you do need to continually access the minimum or maximum, a different data structure may be better.

This package exists for anybody looking, but I recommend benchmarking this against a btree. Generally, a btree is a good and fast data structure. However, a key benefit of heap or mmheap is the ability to modify elements and fix their position in the tree.

For more information about a min-max heap, read this paper.

All of the tests are taken from the stdlib's container/heap package and the Go BSD license is copied into mmheap_test.go` for completeness. As well, the main package-level functions are duplicated, but mostly because there is basically one way to write Push/Pop on a heap. The sift up and sift down functions are new. This repo itself is MIT.

Documentation

Documentation

Overview

Package mmheap provides a drop-in min-max heap for any type that implements heap.Interface.

In a min-max heap, the minimum element is at the root at index 0, and the maximum element is in one of the two root children.

Thus, a min-max heap provides an efficient way to access either the minimum or maximum elements in a set in O(1) time.

Due to the increased number of comparisons to implement a min-heap, its runtime is slower than a general heap (in this implementation, just under 2x). Because of this, unless you need to continually access both the minimum and maximum elements, it may be beneficial to use a different data structure. Even if you do need to continually access the minimum or maximum, a different data structure may be better.

This package exists for anybody looking, but I recommend benchmarking this against github.com/google/btree. Generally, a btree is a good and fast data structure for quickly accessing min and max elements. However, a key benefit of heap or mmheap is the ability to change or modify elements and fix their position in the tree.

For more information about a min-max heap, read the following paper:

http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/MinMaxHeaps.pdf

Since this package is identical to the stdlib's container/heap documentation, it is elided here.

Index

• func Fix(h Interface, i int)
• func Init(h Interface)
• func MaxIndex(h Interface) int
• func Pop(h Interface) interface{}
• func Push(h Interface, x interface{})
• func Remove(h Interface, i int) interface{}
• type Interface

Functions

func Fix

func Fix(h Interface, i int)

func Init

func Init(h Interface)

func MaxIndex

func MaxIndex(h Interface) int

MaxIndex returns the index of the maximum element of the heap.

This is a convenience function that always returns either 0, 1, or 2. This will panic if the heap has no elements.

func Pop

func Pop(h Interface) interface{}

func Push

func Push(h Interface, x interface{})

func Remove

func Remove(h Interface, i int) interface{}

Types

type Interface

type Interface interface {
	heap.Interface
}