Object buckets.Heap
A heap is a binary tree that maintains the heap property: Every node is less than or equal to each of its children. This implementation uses an array as the underlying storage.
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;
}
To create a Max-Heap (greater elements on top) you can a provide a reverse compare function.
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;
}
| Constructor Name and Description |
|---|
|
buckets.Heap(compareFunction)
Creates an empty binary heap.
|
| Method Name and Description |
|---|
|
buckets.Heap.add(element)
Adds the given element into the heap.
|
|
buckets.Heap.clear()
Removes all the elements from the heap.
|
|
buckets.Heap.contains(element)
Returns true if the heap contains the specified element.
|
|
buckets.Heap.equals(other)
Returns true if the binary heap is equal to another heap.
|
|
buckets.Heap.forEach(callback)
Executes the provided function once per element present in the heap in
no particular order.
|
|
buckets.Heap.isEmpty()
Checks if the heap is empty.
|
|
buckets.Heap.peek()
Retrieves but does not remove the root (minimum) element of the heap.
|
|
buckets.Heap.removeRoot()
Retrieves and removes the root (minimum) element of the heap.
|
|
buckets.Heap.size()
Returns the number of elements in the heap.
|
|
buckets.Heap.toArray()
Returns an array containing all the elements in the heap in no
particular order.
|
Object Detail
buckets.Heap(compareFunction)
Creates an empty binary 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
<static>
buckets.Heap.add(element)
Adds the given element into the heap.
- Parameters:
- {*} element
- The element.
- Returns:
- True if the element was added or false if it is undefined.
<static>
buckets.Heap.clear()
Removes all the elements from the heap.
<static>
{boolean}
buckets.Heap.contains(element)
Returns true if the heap contains the specified element.
- Parameters:
- {Object} element
- Element to search for.
- Returns:
- {boolean} True if the Heap contains the specified element, false otherwise.
<static>
{boolean}
buckets.Heap.equals(other)
Returns true if the binary heap is equal to another heap.
Two heaps are equal if they have the same elements.
- Parameters:
- {buckets.Heap} other
- The other heap.
- Returns:
- {boolean} True if the heap is equal to the given heap.
<static>
buckets.Heap.forEach(callback)
Executes the provided function once per element present in the heap in
no particular order.
- Parameters:
- {function(Object):*} callback
- Function to execute, invoked with an element as argument. To break the iteration you can optionally return false.
<static>
{boolean}
buckets.Heap.isEmpty()
Checks if the heap is empty.
- Returns:
- {boolean} True if the heap contains no elements; false otherwise.
<static>
{*}
buckets.Heap.peek()
Retrieves but does not remove the root (minimum) element of the heap.
- Returns:
- {*} The value at the root of the heap. Returns undefined if the heap is empty.
<static>
{*}
buckets.Heap.removeRoot()
Retrieves and removes the root (minimum) element of the heap.
- Returns:
- {*} The removed element or undefined if the heap is empty.
<static>
{number}
buckets.Heap.size()
Returns the number of elements in the heap.
- Returns:
- {number} The number of elements in the heap.
<static>
{Array.<*>}
buckets.Heap.toArray()
Returns an array containing all the elements in the heap in no
particular order.
- Returns:
- {Array.<*>} An array containing all the elements in the heap in no particular order.