deheap

README

deheap

Package deheap provides the implementation of a doubly ended heap. Doubly ended heaps are heaps with two sides, a min side and a max side. Like normal single-sided heaps, elements can be pushed onto and pulled off of a deheap. deheaps have an additional Pop function, PopMax, that returns elements from the opposite side of the ordering.

This implementation has emphasized compatibility with existing libraries in the sort and heap packages.

Performace of the deheap functions should be very close to the performance of the functions of the heap library

Documentation

Overview

Package deheap provides the implementation of a doubly ended heap. Doubly ended heaps are heaps with two sides, a min side and a max side. Like normal single-sided heaps, elements can be pushed onto and pulled off of a deheap. deheaps have an additional Pop function, PopMax, that returns elements from the opposite side of the ordering.

This implementation has emphasized compatibility with existing libraries in the sort and heap packages.

Performace of the deheap functions should be very close to the performance of the functions of the heap library

Example (IntHeap)

This example inserts several ints into an IntHeap, checks the minimum, and removes them in order of priority.

// Example developed by borrowing from "container/heap/example_intheap_test.go"
// Portions Copyright 2012 by the Go authors
//
// This example demonstrates an integer doubbly-ended heap built using the deheap interface.

package main

import (
	"fmt"

	"github.com/aalpar/deheap"
)

// An IntHeap is a min-heap of ints.
type IntDeheap []int

func (h IntDeheap) Len() int           { return len(h) }
func (h IntDeheap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntDeheap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntDeheap) Push(x interface{}) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.(int))
}

func (h *IntDeheap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

// This example inserts several ints into an IntHeap, checks the minimum,
// and removes them in order of priority.
func main() {
	h := &IntDeheap{2, 1, 5, 6}
	deheap.Init(h)
	deheap.Push(h, 3)
	fmt.Printf("minimum: %d\n", (*h)[0])
	for h.Len() > 3 {
		fmt.Printf("%d ", deheap.PopMax(h))
	}
	for h.Len() > 1 {
		fmt.Printf("%d ", deheap.Pop(h))
	}
	fmt.Printf("middle value: %d\n", (*h)[0])
}

Output:

minimum: 1
6 5 1 2 middle value: 3

Index

• func Init(h heap.Interface)
• func Pop(h heap.Interface) interface{}
• func PopMax(h heap.Interface) interface{}
• func Push(h heap.Interface, o interface{})
• func Remove(h heap.Interface, i int) (q interface{})

Examples

• Package (IntHeap)

Functions

func Init

func Init(h heap.Interface)

Init initializes the heap. This should be called once on non-empty heaps before calling Pop(), PopMax() or Push(). See heap.Init()

func Pop

func Pop(h heap.Interface) interface{}

Pop the smallest value off the heap. See heap.Pop(). Time complexity is O(log n), where n = h.Len()

func PopMax

func PopMax(h heap.Interface) interface{}

Pop the largest value off the heap. See heap.Pop(). Time complexity is O(log n), where n = h.Len()

func Push

func Push(h heap.Interface, o interface{})

Push an element onto the heap. See heap.Push() Time complexity is O(log n), where n = h.Len()

func Remove

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

Remove element at index i. See heap.Remove(). The complexity is O(log n) where n = h.Len().