heap

Documentation

Overview

Package heap provides heap operations for any type that implements heap.Interface.

Index

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

Functions

func Init

func Init(h Interface)

A heap must be initialized before any of the heap operations can be used. Init is idempotent with respect to the heap invariants and may be called whenever the heap invariants may have been invalidated. Its complexity is O(n) where n = h.Len().

func Pop

func Pop(h Interface) interface{}

Pop removes the minimum element (according to Less) from the heap and returns it. The complexity is O(log(n)) where n = h.Len(). Same as Remove(h, 0).

func Push

func Push(h Interface, x interface{})

Push pushes the element x onto the heap. The complexity is O(log(n)) where n = h.Len().

func Remove

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

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

Types

type Interface

type Interface interface {
	sort.Interface
	Push(x interface{})
	Pop() interface{}
}

Any type that implements heap.Interface may be used as a min-heap with the following invariants (established after Init has been called):

!h.Less(j, i) for 0 <= i < h.Len() and j = 2*i+1 or 2*i+2 and j < h.Len()