Class Index | File Index

Classes


Class buckets.Heap

A heap is a binary tree, where the nodes maintain the heap property: each node is smaller than each of its children. This implementation uses an array to store elements.

If the inserted elements are custom objects a compare function must be provided, at construction time, otherwise the <=, === and >= operators are used to compare elements. Example:

function compare(a, b) {
 if (a is less than b by some ordering criterion) {
    return -1;
 } if (a is greater than b by the ordering criterion) {
    return 1;
 } 
 // a must be equal to b
 return 0;
}

If a Max-Heap is wanted (greater elements on top) you can a provide a reverse compare function to accomplish that behavior. Example:

function reverseCompare(a, b) {
 if (a is less than b by some ordering criterion) {
    return 1;
 } if (a is greater than b by the ordering criterion) {
    return -1;
 } 
 // a must be equal to b
 return 0;
}

Defined in: <../buckets.js>.

Class Summary
Constructor Attributes Constructor Name and Description
 
buckets.Heap(compareFunction)
Creates an empty Heap.
Method Summary
Method Attributes Method Name and Description
 
add(element)
Adds the given element into the heap.
 
Removes all of the elements from this heap.
 
contains(element)
Returns true if this heap contains the specified element.
 
forEach(callback)
Executes the provided function once for each element present in this heap in no particular order.
 
Checks if this heap is empty.
 
peek()
Retrieves but does not remove the root element of this heap.
 
Retrieves and removes the root element of this heap.
 
size()
Returns the number of elements in this heap.
Class Detail
buckets.Heap(compareFunction)
Creates an empty Heap.
Parameters:
{function(Object|Object):number=} compareFunction
optional function used to compare two elements. Must return a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.
Method Detail
add(element)
Adds the given element into the heap.
Parameters:
{*} element
the element.
Returns:
true if the element was added or fals if it is undefined.

clear()
Removes all of the elements from this heap.

{boolean} contains(element)
Returns true if this heap contains the specified element.
Parameters:
{Object} element
element to search for.
Returns:
{boolean} true if this Heap contains the specified element, false otherwise.

forEach(callback)
Executes the provided function once for each element present in this heap in no particular order.
Parameters:
{function(Object):*} callback
function to execute, it is invoked with one argument: the element value, to break the iteration you can optionally return false.

{boolean} isEmpty()
Checks if this heap is empty.
Returns:
{boolean} true if and only if this heap contains no items; false otherwise.

{*} peek()
Retrieves but does not remove the root element of this heap.
Returns:
{*} The value at the root of the heap. Returns undefined if the heap is empty.

{*} removeRoot()
Retrieves and removes the root element of this heap.
Returns:
{*} The value removed from the root of the heap. Returns undefined if the heap is empty.

{number} size()
Returns the number of elements in this heap.
Returns:
{number} the number of elements in this heap.

Documentation generated by JsDoc Toolkit 2.4.0 on Sun Jan 29 2012 14:10:49 GMT-0500 (COT)