rlheap

Documentation

Overview

Package heap provides heap operations for any type that implements heap.Interface. A heap is a tree with the property that each node is the minimum-valued node in its subtree.

A heap is a common way to implement a priority queue. To build a priority queue, implement the Heap interface with the (negative) priority as the ordering for the Less method, so Push adds items while Pop removes the highest-priority item from the queue. The Examples include such an implementation; the file example_pq_test.go has the complete source.

Index

• func Down(h heap.Interface, i, j int)
• func Init(h heap.Interface)
• func Pop(h heap.Interface) interface{}
• func Push(h heap.Interface, x interface{})
• func RegularDown(h heap.Interface, i, j int)
• func RegularSort(h heap.Interface)
• func Remove(h heap.Interface, i int) interface{}
• func Sort(h heap.Interface)

Functions

func Down

func Down(h heap.Interface, i, j int)

func Init

func Init(h heap.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 heap.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 heap.Interface, x interface{})

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

func RegularDown

func RegularDown(h heap.Interface, i, j int)

func RegularSort

func RegularSort(h heap.Interface)

func Remove

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

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

func Sort

func Sort(h heap.Interface)