Resizable Binary Heap
Installation
npm install binaryheap-resizable
Testing
npm test
Simple usage
var maxHeap = ; orvar maxHeap = ;// set it up as a simple max-heap// its initial length is 3 and its initial data is the maxHeapified// version of the passed array var minObjectHeap = ; orvar minObjectHeap = ;// set it up as a object min-heap of initial length equals to 4// compare objects from the heap by their priority property// when inserted/pulled, throw an error if property does not exist
API
Constructors
constructor(initial-length)
- build an empty heap withinitial-length
size.constructor(array)
- heapifyarray
. initial length is set toarray.length
.
Predicates
predicate().greater([ property [, default]])
- set heap as max-heap. ifproperty
is set, elementsproperty
values will be used when comparing. if this value is not accessible anddefault
is set,default
will be used instead.predicate().lesser([ property [, default]])
- same as above, but it will set heap as min-heap.predicate(fn).value([ property [, default]])
- same as above, but it will usefn
as the predicatemaxHeap()
- alias forpredicate().greater()
minHeap()
- alias forpredicate().lesser()
Data management methods
insert(elements..), insert(array-of-elements)
- insert all passed elements in the heap, doing reallocations if necessary. returns new heap size. aliaspush()
.peek()
- return the root element of the heap or null if heap is empty.pull()
- peek and remove the peeked element from the heap if its not null. aliaspop()
resizeFactor([factor])
- get/set how much the heap buffer will expand/shrink when needed. default is2
.resize(n)
- manually resize the heap buffer ton
.toArray()
- return an array representation of the heap
Properties
size
- store how many elements are on the heap.length
- get the length of the heap buffer.
What package is that?
Exactly what the package name says it is. It's a resizable binary heap.
What do you exactly mean by resizable?
With binaryheap-resizable
you can pre-allocate an array space for your binary heap with no worrying about when it's gonna be fulfilled. It expands and shrink itself automatically as elements are inserted to/pulled from the heap. You can even resize it by yourself using the resize()
member method!
But what? I don't want my application to be re-allocating memory for a heap all the time!
That's why binaryheap-resizable
got a resizeFactor
property. Every time the heap data array is expanded, it's expanded to BinaryHeap.length * resizaFactor
. You specify how much your array will be expanded/shrinked, so depending on your array initial size and on your demands you can control how often the application will be re-allocating memory to the heap. resizeFactor
default value is 2
.
Ok. Since it's a binary heap, how can I control the ordering criteria?
The heap constructor has an argument called predicate
. You can set the binary heap predicate by passing a function fn(a, b)
as that argument, where a
is the parent element and b
is its child. By default binaryheap-resizable
has a predicate
set to a max-heap predicate.
var { return a > b;}
So we have a pseudo-code which:
predicate(top-element, child-n) is truthy for n 1..top-element-child-count
So in version 0.0.7
we introduced new ways of handling predicates. We will be discussing about them right below.
Multiple ways of handling predicates
>= 0.0.7
In older versions we had only the basic way of dealing with predicates. It was really hard to deal with errors and to keep things going smooth when going through non-existent objects. Version 0.0.7
introduced major changes related to the way predicates were set up. It's important to say that projects that were built on top of older versions are still perfectly compatible with this new version.
Default method, in constructor
The old version way is still available but we highly recommend you to avoid it for non-number objects. Here's the min-heap predicate example.
var { return a < b;} var heap = 4 predicate;// create a min-heap with initial capacity of 4
This method can not handle object properties very well.
Deep finding way
In 0.0.7
the functional way of handling predicates was introduced. It's now simple to define your predicate and control the behavior of your application when dealing with deep objects. Let's say you want to order a max-heap by their priority
properties. In the old fashioned way you would do something like this:
// old deprecated wayvar { return apriority > bpriority;} var heap = 4 predicate;// you will probably have problems dealing with non-existent objects or null properties
You could avoid the problems by rewriting your predicate
code to check for these problems before doing the real job. But it's just awful. Then we introduce you a clean way of dealing with these issues.
// a and b are now real valuesvar { return a < b;} // BinaryHeap(capacity).predicate(predicate).value([path [, default-value]])// value() function returns a BinaryHeap object reference that can be used var heap1 = value'priority';var heap2 = value'priority' 1;// heap1 inserts and pulls may throw an error when priority property does not exist// heap2 inserts and pulls will set a default value to be compared when priority property does not exist
This code does basically what the deprecated code does, but you can define a solid behavior when dealing with properties passing a path
argument to deep find that property, or even pass a default-value
argument to be set as default value when a property does not exist, avoiding access errors.
When comparing it does something like this: (pseudo-code):
// heap1apriority < bpriority or throw an error if property priority does not exist// heap2apriority < bpriority if property priority exists in both objects or1 < bpriority if property priority exists only in b object orapriority < 1 if property priority exists only in a object or1 < 1 if property priority does not exist in both objects
Preset-based way
The preset-based way is just what we described above, passing no arguments to predicate
and using greater()
and lesser()
in place of value()
. Using this we can quickly build max/min-heaps from raw numbers or numbers from deep objects properties.
var heap1 = ;// max-heap comparing (a.priority or 1) > (b.priority or 1)var heap2 = ;// min-heap comparing (a.info.relevance or 2) < (b.info.relevance or 2)
We can also use the aliases to predicate().greater()
and predicate().lesser()
var heap1 = ;// max-heap comparing (a.priority or 1) > (b.priority or 1)var heap2 = ;// min-heap comparing (a.info.relevance or 2) < (b.info.relevance or 2)