class Heap

pub class Heap<T :: [TotalOrder]>

Conforms to FromArrayLiteral<T>, Debug, FromIterator<T>, Clone.

A binary min-heap: Heap.peek and Heap.pop give the least value.

push and pop take log n steps, peek constant time; the values lie in a list. For the greatest value first, use a type whose order is reversed. Not safe across threads.

Methods

pub static fn new(): Heap<T>

Creates an empty heap.

pub static fn withCapacity(n: int): Heap<T>

Creates an empty heap with room for n values before it grows.

Panics

When n is negative.

pub static fn of(xs: T[]): Heap<T>

Creates a heap of the array's values, copied.

Builds the heap in linear time by sinking each parent to its place, from the last one up (Floyd's method); pushing the values one by one would take n log n.

pub fn length(): int

Returns how many values it holds.

pub fn isEmpty(): bool

Returns whether it holds no values.

pub fn peek(): ?T

Returns the least value without removing it, or null where there is none.

pub mut fn push(v: T): void

Adds v, letting it rise to its place, in log n steps.

pub mut fn pop(): ?T

Removes and returns the least value, or null where there is none.

The last value is put at the top and sunk to its place, in log n steps.

static fn fromLiteral(items: T[]): Heap<T>

fn debug(): string

fn debugTo(out: StringBuilder): void

static fn fromIter<I :: [Iterator<Item = T>]>(it: I): Heap<T> throws I.Error

Creates a heap of the iterator's values, built at once as Heap.of does.

Errors

Throws what a pull of it throws.

fn clone(): Heap<T>