binomial-heap
No dependency binomial heap, compatible with typescript, can have custom compare function.
Can merge and push different primitive types into the heap, after which it will do automatic sanity check and restructure itself.
Algoritm costs should be standard for binomial heap. If not, please consider adding a task / pull request.
This heap is fully typed, including multi-type heaps. Heaps which contain strings, numbers and/or Dates do not need custom compare function. Heaps which contain objects have to use custom compare.
Examples (from unit tests):
Basic numerical heap sort:
expect heap.sort.toEqual.sorta - b;
Type combination heap sort:
;expectheapdates.sort.toEqualdates.sortnew Datea.getTime - new Dateb.getTime;
Can merge two types of variables / two heaps of different types (Sanity check is O(n), won't happen unless necessary):
expect heap.sort.mapitem.toString.toEqual.sorta.toString.localeCompareb.toString.mapitem.toString; expect heap.mergeheap.sort.mapitem.toString.toEqual.sorta.toString.localeCompareb.toString.mapitem.toString;
The heap also supports these operations: pop (deletes minimum), push, search, delete, compare (sets up a new compare function).
Examples of compare and search/delete (both search and delete accept a function or item as an argument):
;expecttest.items.toEqual;expecttest.compareMath.absa - Math.absb.items.toEqual; ;expectheapdates.searchnew Dateitem.getTime === dates.toEqualdates; ;expectheapdates.deletenew Dateitem.getTime === dates.toEqualdates;
Changes since 1.0.1
Binomial heap now has an inner representation of tree instead of array. Done this in order to fix linear cost merge operation.
Changes since 1.1.0
Binomial heap now can be converted into a promisified heap, returning promises for each operation.
Also, fixed a bug in pop function. Added appropriate unit tests.
Changes since 1.2.0
Package now extends array interface to allow you to convert it to heap.
Changes since 1.3.0
Package now allows for a short-hand definition of compare function (one parameter is enough, will be converted to: (a, b) => fn(a) - fn(b)).
Example
;;expectheaparray, Math.abs.sort.toEqualarray.sortabsSort;expectheaparray.compareMath.abs.sort.toEqualarray.sortabsSort;
Footer
If you encounter any bugs, or have ideas for improvement, do not hesitate to add a task or a pull request.