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 `[2*n]`

and Right at `[2*n + 1]`

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

## Api

### new Heap( options )

create a new empty heap.Options:

`comparBefore`

: a fast comparison function that returns true when the first

`compar`

below. The default is `function(a,b) { return a < b }`

.`compar`

: comparison function to determine the item ordering. The function

`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

`size`

: the initial capacity of the heap. The heap is extended as needed,

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

`compar`

.### insert( item ), push( item ), enqueue( item )

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.### remove( ), shift( ), dequeue( )

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.### peek( )

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

.### length

the heap`length`

property is the count of items currently in the heap. This
is a read-only property, it must not be changed.### gc( options )

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.

`minFull`

- do not resize arrays that are more full than this fraction.

## 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

## 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