Module: stdgo.container.heap

(view library index)

Overview

Index

• class Heap

• function fix(_h:stdgo.container.heap.Interface, _i:Int):Void

• function init(_h:stdgo.container.heap.Interface):Void

• function pop(_h:stdgo.container.heap.Interface):stdgo.AnyInterface

• function push(_h:stdgo.container.heap.Interface, _x:stdgo.AnyInterface):Void

• function remove(_h:stdgo.container.heap.Interface, _i:Int):stdgo.AnyInterface

• typedef Interface

Classes

import

class Heap

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.

The minimum element in the tree is the root, at index 0.

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.

Heap function fix

function fix(_h:stdgo.container.heap.Interface, _i:Int):Void

Fix re-establishes the heap ordering after the element at index i has changed its value.
        Changing the value of the element at index i and then calling Fix is equivalent to,
        but less expensive than, calling Remove(h, i) followed by a Push of the new value.
        The complexity is O(log n) where n = h.Len().

(view code)

Heap function init

function init(_h:stdgo.container.heap.Interface):Void

Init establishes the heap invariants required by the other routines in this package.
        Init is idempotent with respect to the heap invariants
        and may be called whenever the heap invariants may have been invalidated.
        The complexity is O(n) where n = h.Len().

(view code)

Heap function pop

function pop(_h:stdgo.container.heap.Interface):stdgo.AnyInterface

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

(view code)

Heap function push

function push(_h:stdgo.container.heap.Interface, _x:stdgo.AnyInterface):Void

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

(view code)

Heap function remove

function remove(_h:stdgo.container.heap.Interface, _i:Int):stdgo.AnyInterface

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

(view code)

Typedefs

import

typedef Interface

typedef Interface = stdgo._internal.container.heap.Interface;