qheap

qheap
=====


Qheap is a very fast classic heap / priority queue.

A heap is partially ordered balanced binary tree with the property that the
value at the root comes before any value in either the left or right subtrees.
It supports two operations, insert and remove, both O(log n) (and peek, O(1)).
The tree can be efficiently mapped into an array: the root at offset [1] and
each node at [n] having children Left at [2n] and Right at [2n + 1].

var Heap = require('qheap');
var h = new Heap();
h.insert('c');
h.insert('a');
h.insert('b');
h.remove(); // => 'a'

Api
---

$3

create a new empty heap.

Options:

- comparBefore: a fast comparison function that returns true when the first
argument should be sorted before the second. This comparator runs much faster than
the three-way compar below. The default is function(a,b) { return a < b }.
- compar : comparison function to determine the item ordering. The function
should return a value less than zero if the first argument should be ordered
before the second (compatible with the function passed to sort()). The
default ordering if no compar is specified is by <: function(a,b){ return
a < b ? -1 : 1 }

- freeSpace : when the heap shrinks to 1/4 its high-water mark, reallocate the
storage space to free the unused memory, and reset the high-water mark.
Default is false, avoiding the overhead of the array slice. Note: freeing
space from the array halves the insert rate; use advisedly.

- size : the initial capacity of the heap. The heap is extended as needed,
but for debugging dumps it can be useful to specify a smaller starting size than
the default 100.

If options is a function, it is taken to be the comparison function compar.

$3

insert the item into the heap and rebalance the tree. Item can be anything,
only the compar function needs to know the actual type.
Push is an alias for insert.

$3

remove and return the item at the root of the heap (the next item in the
sequence), and rebalance the tree. When empty, returns undefined.
Shift is an alias for remove.

$3

return the item at the root of the heap, but do not remove it. When empty,
returns undefined.

$3

the heap length property is the count of items currently in the heap. This
is a read-only property, it must not be changed.

$3

Resize the storage array to free all unused array slots. The options, if
specified, control when to gc for more efficient operation.

Options:

- minLength - do not resize arrays smaller than this cutoff.
Default 0, resize even the smallest arrays.
- minFull - do not resize arrays that are more full than this fraction.
Default 1.00, resize unless 100% full.

Performance
-----------

Running the fastpriorityqueue benchmark:

function rand(i) {
i = i + 10000;
i = i ^ (i << 16);
i = (i >> 5) ^ i ;
return i & 0xFF;
}
function testLoop() {
var i, b = new qheap();
for (i = 0; i < 128; i++) { b.insert(rand(i)) }
for (i = 128; i < 1280; i++) { b.insert(rand(i)) ; b.remove() }
}

new heap + 128 inserts + 1152 insert/removes
qtimeit=0.19.0 node=6.10.2 v8=5.1.281.98 platform=linux kernel=3.16.0-4-amd64 up_threshold=11
arch=ia32 mhz=4419 cpuCount=8 cpu="Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz"
name speed rate
jsprioqueue 6,037 ops/sec 1000 >>>>>
heap 29,913 ops/sec 4955 >>>>>>>>>>>>>>>>>>>>>>>>>
fastpriorityqueue 38,264 ops/sec 6338 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
qheap 41,139 ops/sec 6814 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

Todo
----

- might be more efficient to periodically gc the heap on a timer instead of checking
on every remove

Related Work
------------

- heap - the classic, slow with custom comparator
- qheap, this - very fast heap and priority queue
- fastpriorityqueue - very fast, includes comprehensive list nodejs heaps
- qlist - very fast circular buffer