heap

module HeapMixin

Since Enumerable defines min and max, we must use a mixin to ensure that we get our own min/max.

Public Methods

min

Find item with the smallest key, in O(1) time.

Returns: an array containing the key and value of the smallest item, or nil if the heap is empty.

first

Find item with the smallest key, in O(1) time.

Returns: the value of the smallest item, or nil if the heap is empty.

max

Find the item with the largest key, in O(n) time.

Returns: an array containing the key and value of the largest item, or nil if the heap is empty.

last

Find the item with the largest key, in O(n) time.

Returns: an array containing the key and value of the largest item, or nil if the heap is empty.

class Heap < Object

Also known as a PriorityQueue, a Heap is a container of key/value pairs, where the key represents a priority level. This particular Heap has been written to work the same way as a SortedHash (that is, smaller keys have higher priority). A Hash will probably be faster for most operations; use a Heap only when you need the shift() operation (which a Hash does not provide).

TODO: This is a binary heap; should we name it that way?

Public Methods

default

default=

initialize(capacity=0, impl_class=Array)

Create a new Heap

capacity	the initial size of the heap.
impl_class	usually array, but can be any class that is compatible with Array.

self.[](hash)

Determine whether a Heap is empty.

Public Methods

store(key, value)

Add a new item to the heap.

key	the priority of the item to add (lower values have higher priority).
value	the item to add.

Returns: The value of the item that was added.

[]=

[]= is an alias for store.

[](key)

Given a key, find a value, in O(n) time.

key	the key to search for.

Returns: the first value found with the given keym or @default if no such value is found.

fetch(key, default=NIL)

shift()

Remove the smallest item from the heap, in O(log n) time.

Returns: an array containing the key and value of item that was deleted.

pop()

Remove the largest item from the heap, in O(n) time.

Returns: an array containing the key and value of the item that was deleted, or nil if the heap is empty.

clear

Clear a heap. Has the side-effect of changing the capacity to 0.

Returns: self.

clone

each(index=1, &block)

Iterate through all the elements of the heap, in order. This method allocates a new heap to do the iteration, so it may not be very fast.

Returns: the value from the last call to yield.

each_pair

each_pair is an alias for each.

size

length

length is an alias for size.

Mixins

Enumerable
HeapMixin
EnumerableContainer
PairEnumerableContainer
IndexableContainer

Protected Methods

impl_class

impl_class=

arr

arr=

size=

percolate_up(i)

Percolate the item at position i up to its appropriate position.

percolate_down(i)

Percolate the item at position i down to its approriate position

Constants

NIL

Requires