js_cols Class: IntervalHeap

new IntervalHeap(compare_func)

js_cols.IntervalHeap is a double-ended Priority Queue, based on a Binary Heap. This allows deleteMin and deleteMax in at O(logn) running time, and also efficiently keeps track of the current interval contained in the queue. This IntervalHeap is addressable, i.e. a handle is returned when inserting an element. The handles are used for efficient remove and change key operations, both in time O(logn). Algorithms are adaptations of those in J. van Leeuwen and D. Wood Interval Heaps.

The big-O notation for all operations are below:

  Method                 big-O
----------------------------------------------------------------------------
- changeKey              O(logn)
- clear                  O(1)
- clone                  O(n)
- deleteMin              O(logn)
- deleteMax              O(logn)
- getKeys                O(n)
- getValues              O(n)
- insert                 O(logn)
- insertAll              O(n logn)
- max                    O(1)
- min                    O(1)
- remove                 O(logn)

Parameters:

Name	Type	Argument	Description
`compare_func`	function	<optional>	an optional compare function to compare the keys. This function should take two values, a and b, and return x where: x < 0 if a < b, x > 0 if a > b, x = 0 otherwise if not defined, a default compare function for `numbers` will be used

Classes

Handle

Methods

changeKey(handle, newKey) → {boolean}

Changes the key for the value associated with the supplied handle

Parameters:

Name	Type	Description
`handle`	js_cols.IntervalHeap.Handle	the handle to use for location of the value
`newKey`	*	the new key to associate with the value

Returns:

true if the handle was valid for this heap, and the key was successfully changed, otherwise false

Type: boolean

clear()

Removes all key/value pairs from the heap

clone() → {js_cols.IntervalHeap}

Returns a shallow clone of this heap

Returns:

Type: js_cols.IntervalHeap

deleteMax() → {*}

Removes and returns the value associated with the maximum key in the queue

Returns:

the value associated with the maximum key in the queue

Type: *

deleteMin() → {*}

Removes and returns the value associated with the minimum key in the queue

Returns:

the value associated with the minimum key in the queue

Type: *

getCount() → {number}

Returns the number of key/value pairs in the Priorityqueue

Returns:

Type: number

getKeys() → {Array}

Returns an array with the keys of this heap. NOTICE: The returned array is unordered

Returns:

Type: Array

getValues() → {Array}

Returns an array with the values of this heap. NOTICE: The returned array is unordered

Returns:

Type: Array

insert(k, v) → {js_cols.IntervalHeap.Handle}

Inserts a value prioritized after the supplied key

Parameters:

Name	Type	Description
`k`	*	the priority key
`v`	*	the value to insert

Returns:

a Priority Queue Handle, used for later changeKey or remove operations

Type: js_cols.IntervalHeap.Handle

insertAll(col)

Inserts a collection of key/value pairs into the map If the collection has no notion of keys (i.e. an Array or Set) each element is inserted as both key and value (mapping to it self)

Parameters:

Name	Type	Description
`col`

isEmpty() → {boolean}

Returns true if theres zero key/ value pairs in the heap

Returns:

Type: boolean

max() → {*}

Returns the value associated with the maximum key of the queue

Returns:

the value associated with the maximumkey

Type: *

min() → {*}

Returns the value associated with the minimum key of the queue

Returns:

the value associated with the minimum key

Type: *

remove(handle) → {boolean}

Removes the value associated with the supplied handle

Parameters:

Name	Type	Description
`handle`	js_cols.IntervalHeap.Handle	the handle to use for location of the value

Returns:

true if the handle was valid for this heap, and the value was successfully removed, otherwise false

Type: boolean