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>.
Constructor Attributes | Constructor Name and Description |
---|---|
buckets.Heap(compareFunction)
Creates an empty Heap.
|
Method Attributes | Method Name and Description |
---|---|
add(element)
Adds the given element into the heap.
|
|
clear()
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.
|
|
isEmpty()
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.