ES6 implementation of the binomial heap data structure with TypeScript support.
Visit the contributing guidelines to learn more on how to translate this document into more languages.
yarn add binoheap
npm install binoheap
A binomial heap data structure, is a specific implementation of the heap data structure, comprised of collections of binomial trees that are linearly linked together, where each tree is a minimum or maximum ordered heap. Binomial heaps are similar to binary heaps but they have a more specific structure and allow for efficient O(log n) heap merging.
A binomial heap is implemented as a set of binomial trees, compared to a binary heap that has the shape of a single binary tree, which are defined recursively as follows:
0 is a single node.k has a root node whose children are roots of binomial trees of orders k−1, k−2, ..., 2, 1, 0.A binomial tree of order k has 2^k nodes and height k. Because of its unique structure, a binomial tree of order k can be constructed from two trees of order k−1 by attaching one of them as the leftmost child of the root of the other. This feature is central to the merge operation of a binomial heap, which is its major advantage over other conventional heaps.
Additionally, each tree in the binomial heap should satisfy the binomial heap properties:
The first property implies that a binomial heap with n nodes consists of at most 1 + log2 n binomial trees. The second property ensures that the root of each binomial tree contains the smallest or the largest key in the tree, which applies to the entire heap.
Binoheap binomial heaps are implemented using doubly linear linked lists for storing nodes, thus parent nodes point directly to their children and the child nodes point back to their parent. Each node contains a parent, sibling & child pointer, as well as a key, a value and a degree property.
Binoheap exposes a chainable API, that can be utilized through a simple and minimal syntax, allowing you to combine methods effectively.
To create a min-ordered binomial heap, where the nodes of each binomial tree obey the min-heap property, according to which the parent node is always smaller than or equal to its children nodes, we provide as argument to the Heap class, on instantiation, a binary comparator function compareMin(x, y), which returns a positive number when the node x is greater than node y, zero when equal and a negative number when less than.
Additionally, to create a max-ordered binomial heap, where the nodes of each binomial tree obey the max-heap property, according to which the parent node is always greater than or equal to its children nodes, we provide as argument to the Heap class, on instantiation, a binary comparator function compareMax(x, y), which returns a negative number when the node x is greater than the node y, zero when equal and a positive number when less than.
By default, if no comparator function is provided on instantiation, a min-ordered binomial heap instance is returned, where the key value of each node is used for maintaining the min-heap property by the comparator function.
Usage examples can be also found at the test directory.
'use strict';
const {Heap, Node} = require('binoheap');
// Create a max-ordered binomial heap
const heap = new Heap((x, y) => y.key - x.key);
heap.isEmpty();
//=> true
heap.insert(1, 'A');
//=> Heap {
// size: 1,
// head: Node { key: 1, value: 'A', degree: 0, parent: null, child: null, sibling: null } }
heap.isEmpty();
//=> false
heap.size;
//=> 1
heap.head;
//=> Node { key: 1, value: 'A', degree: 0, parent: null, child: null, sibling: null }
heap.head.toPair();
//=> [1, 'A']
const node = new Node(1, 'A');
//=> Node { key: 1, value: 'A', degree: 0, parent: null, child: null, sibling: null }
heap.head.key === node.key;
//=> true
heap.head.value === node.value;
//=> true
heap.head.degree === node.degree;
//=> true
heap
.insert(2, 'B')
.insert(3, 'C')
.insert(4, 'D')
.insert(5, 'E')
.insert(6, 'F')
.insert(7, 'G');
//=> Heap {
// size: 7,
// head: Node { key: 7, value: 'G', degree: 0, parent: null, child: null, sibling: [Node] } }
heap.head.siblings();
//=> [
// Node { key: 6, value: 'F', degree: 1, parent: null, child: [Node], sibling: [Node] },
// Node { key: 4, value: 'D', degree: 2, parent: null, child: [Node], sibling: null }
// ]
// Returns the node with the maximum key value
heap.extremum();
//=> Node { key: 7, value: 'G', degree: 0, parent: null, child: null, sibling: [Node] }
heap.extremumKey();
//=> 7
heap.extremumValue();
//=> 'G'
heap.roots();
//=> [
// Node { key: 7, value: 'G', degree: 0, parent: null, child: null, sibling: [Node] },
// Node { key: 6, value: 'F', degree: 1, parent: null, child: [Node], sibling: [Node] },
// Node { key: 4, value: 'D', degree: 2, parent: null, child: [Node], sibling: null }
// ]
heap.includes(100);
//=> false
heap.includes(2);
//=> true
heap.search(1);
//=> Node { key: 1, value: 'A', degree: 0, parent: [Node], child: null, sibling: null }
heap.search(20);
//=> undefined
// Remove and return the node with the maximum key value
heap.removeExtremum();
//=> Node { key: 7, value: 'G', degree: 0, parent: null, child: null, sibling: [Node] }
heap.head;
//=> Node { key: 6, value: 'F', degree: 1, parent: null, child: [Node], sibling: [Node] }
heap.size;
//=> 6
const heap2 = new Heap((x, y) => y.key - x.key));
heap2
.insert(8, 'H')
.insert(9, 'I');
//=> Heap {
// size: 2,
// head: Node { key: 9, value: 'I', degree: 1, parent: null, child: [Node], sibling: null } }
heap2.updateKey(8, 15);
//=> Heap {
// size: 2,
// head: Node { key: 15, value: 'H', degree: 1, parent: null, child: [Node], sibling: null } }
heap.merge(heap2);
//=> Heap {
// size: 8,
// head: Node { key: 15, value: 'H', degree: 3, parent: null, child: [Node], sibling: null } }
heap.head.descendants();
//=> [
// Node { key: 4, value: 'D', degree: 2, parent: [Node], child: [Node], sibling: [Node] }
// Node { key: 2, value: 'B', degree: 1, parent: [Node], child: [Node], sibling: [Node] },
// Node { key: 1, value: 'A', degree: 0, parent: [Node], child: null, sibling: null },
// ]
headNode | nullReturns the head node of the heap. If the heap is empty then null is returned.
const {Heap} = require('binoheap');
const heap = new Heap();
heap.insert(10, 'A');
//=> Heap {
// size: 1,
// head: Node { key: 10, value: 'A', degree: 0, parent: null, child: null, sibling: null } }
heap.head;
// => Node { key: 10, value: 'A', degree: 0, parent: null, child: null, sibling: null }
sizeNumberReturns the total number of nodes residing in the heap.
const {Heap} = require('binoheap');
const heap = new Heap();
heap
.insert(10, 'A')
.insert(20, 'B')
.insert(30, 'C');
//=> Heap {
// size: 3,
// head: Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] } }
heap.size;
// => 3
clear()HeapMutates the heap by removing all residing nodes and returns it empty.
const {Heap} = require('binoheap');
const heap = new Heap();
heap
.insert(10, 'A')
.insert(20, 'B')
.insert(30, 'C');
//=> Heap {
// size: 3,
// head: Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] } }
heap.size;
// => 3
heap.clear();
//=> Heap {
// size: 0,
// head: null }
heap.size;
//=> 0
extremum()Node | undefinedReturns the node corresponding to the minimum key value, if the heap is minimum-ordered or the node corresponding to the maximum key, if the heap is maximum-ordered. If the heap is empty then undefined is returned.
const {Heap} = require('binoheap');
// Create a minimum-ordered heap
const minHeap = new Heap((x, y) => x.key - y.key);
minHeap
.insert(10, 'A')
.insert(20, 'B')
.insert(30, 'C');
//=> Heap {
// size: 3,
// head: Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] } }
minHeap.extremum();
//=> Node { key: 10, value: 'A', degree: 1, parent: null, child: [Node], sibling: null }
// Create a maximum-ordered heap
const maxHeap = new Heap((x, y) => y.key - x.key);
maxHeap
.insert(10, 'A')
.insert(20, 'B')
.insert(30, 'C');
//=> Heap {
// size: 3,
// head: Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] } }
maxHeap.extremum();
//=> Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] }
extremumKey()Number | undefinedReturns the minimum key value, if the heap is minimum-ordered or the maximum key value, if the heap is maximum-ordered. If the heap is empty then undefined is returned.
const {Heap} = require('binoheap');
// Create a minimum-ordered heap
const minHeap = new Heap((x, y) => x.key - y.key);
minHeap
.insert(10, 'A')
.insert(20, 'B')
.insert(30, 'C');
//=> Heap {
// size: 3,
// head: Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] } }
minHeap.extremumKey();
//=> 10
// Create a maximum-ordered heap
const maxHeap = new Heap((x, y) => y.key - x.key);
maxHeap
.insert(10, 'A')
.insert(20, 'B')
.insert(30, 'C');
//=> Heap {
// size: 3,
// head: Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] } }
maxHeap.extremumKey();
//=> 30
extremumValue()Any | undefinedReturns the value corresponding to the node with the minimum key in the heap, if the heap is minimum-ordered or the value corresponding to the node with the maximum key, if the heap is maximum-ordered. If the heap is empty then undefined is returned.
const {Heap} = require('binoheap');
// Create a minimum-ordered heap
const minHeap = new Heap((x, y) => x.key - y.key);
minHeap
.insert(10, 'A')
.insert(20, 'B')
.insert(30, 'C');
//=> Heap {
// size: 3,
// head: Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] } }
minHeap.extremumValue();
//=> 'A'
// Create a maximum-ordered heap
const maxHeap = new Heap((x, y) => y.key - x.key);
maxHeap
.insert(10, 'A')
.insert(20, 'B')
.insert(30, 'C');
//=> Heap {
// size: 3,
// head: Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] } }
maxHeap.extremumKey();
//=> 'C'
heapTrees()NumberReturns the number of binomial trees that the heap is comprised of.
const {Heap} = require('binoheap');
const heap = new Heap();
heap
.insert(10, 'A')
.insert(20, 'B')
.insert(30, 'C');
//=> Heap {
// size: 3,
// head: Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] } }
heap.heapTrees();
//=> 2
includes(key)BooleanTraverses the nodes in the binomial heap level by level, from left to right & from top to bottom, and determines whether the heap includes a node with the given key value, returning true or false as appropriate.
keyNumberNode key to search for.
const {Heap} = require('binoheap');
const heap = new Heap();
heap
.insert(10, 'A')
.insert(20, 'B')
.insert(30, 'C');
//=> Heap {
// size: 3,
// head: Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] } }
heap.includes(20);
//=> true
heap.includes(5);
//=> false
insert(key, value)HeapMutates the heap by inserting a new node at the appropriate location. Returns the heap itself.
keyNumberCan be any number that will correspond to the key of the created node.
valueAnyCan be any value that will stored in the created node.
const {Heap} = require('binoheap');
const heap = new Heap();
heap.insert(10, 'A');
//=> Heap {
// size: 1,
// head: Node { key: 10, value: 'A', degree: 0, parent: null, child: null, sibling: null } }
heap
.insert(20, 'B')
.insert(30, 'C');
//=> Heap {
// size: 3,
// head: Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] } }
isEmpty()BooleanDetermines whether the heap is empty, returning true or false as appropriate.
const {Heap} = require('binoheap');
const heap = new Heap();
heap.isEmpty();
// => true
heap.insert(10, 'A');
//=> Heap {
// size: 1,
// head: Node { key: 10, value: 'A', degree: 0, parent: null, child: null, sibling: null } }
heap.isEmpty();
// => false
merge(heap)HeapMutates the Heap instance by merging it with the given binomial heap. Returns the resulting merged heap.
heapHeapHeap to merge with the Heap instance.
const {Heap} = require('binoheap');
const heap1 = new Heap();
heap1
.insert(10, 'A')
.insert(20, 'B')
.insert(30, 'C');
//=> Heap {
// size: 3,
// head: Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] } }
const heap2 = new Heap();
heap2
.insert(40, 'D')
.insert(50, 'E')
.insert(60, 'F');
//=> Heap {
// size: 3,
// head: Node { key: 60, value: 'F', degree: 0, parent: null, child: null, sibling: [Node] } }
heap1.merge(heap2);
//=> Heap {
// size: 6,
// head: Node { key: 30, value: 'C', degree: 1, parent: null, child: [Node], sibling: [Node] } }
removeExtremum()Node | undefinedMutates the heap by removing the node corresponding to the minimum key value, if the heap is minimum-ordered or the node corresponding to the maximum key if the heap is maximum-ordered.
The removed node is returned by the method if the heap is not empty. If the heap is empty then undefined is returned instead.
keyNumberCan be any number that corresponds to the key of an existing node.
const {Heap} = require('binoheap');
// Create a minimum-ordered heap
const minHeap = new Heap((x, y) => x.key - y.key);
minHeap
.insert(10, 'A')
.insert(20, 'B')
.insert(30, 'C');
//=> Heap {
// size: 3,
// head: Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] } }
minHeap.removeExtremum();
//=> Node { key: 10, value: 'A', degree: 1, parent: null, child: [Node], sibling: null }
minHeap;
//=> Heap {
// size: 2,
// head: Node { key: 20, value: 'B', degree: 1, parent: null, child: [Node], sibling: null } }
// Create a maximum-ordered heap
const maxHeap = new Heap((x, y) => y.key - x.key);
maxHeap
.insert(10, 'A')
.insert(20, 'B')
.insert(30, 'C');
//=> Heap {
// size: 3,
// head: Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] } }
maxHeap.removeExtremum();
//=> Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] }
maxHeap;
//=> Heap {
// size: 2,
// head: Node { key: 20, value: 'B', degree: 1, parent: null, child: [Node], sibling: null } }
roots()Array<Node>Traverses the root nodes of the binomial trees residing in the heap and stores of each traversed root node in an array. At the end of the traversal, the method returns the array which will contain all tree root nodes in ascending degree order.
const {Heap} = require('binoheap');
const heap = new Heap();
heap
.insert(10, 'A')
.insert(20, 'B')
.insert(30, 'C');
//=> Heap {
// size: 3,
// head: Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] } }
heap.roots();
//=> [
// Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] },
// Node { key: 10, value: 'A', degree: 1, parent: null, child: [Node], sibling: null }
// ]
search(key)Node | undefinedTraverses the nodes in the binomial heap level by level, from left to right & from top to bottom, and determines whether the heap includes a node with the given key value, returning node itself, without mutating the heap, or undefined as appropriate.
keyNumberNode key to search for.
const {Heap} = require('binoheap');
const heap = new Heap();
heap
.insert(10, 'A')
.insert(20, 'B')
.insert(30, 'C');
//=> Heap {
// size: 3,
// head: Node { key: 30, value: 'C', degree: 0, parent: null, child: null, sibling: [Node] } }
heap.search(10);
//=> Node { key: 10, value: 'A', degree: 1, parent: null, child: [Node], sibling: null }
heap.includes(5);
//=> undefined
updateKey(key, newKey)HeapTraverses the nodes in the binomial heap level by level, from left to right & from top to bottom, and determines whether the heap includes a node with the given key value. If the node is found then, its key value is mutated by replacing it with the new newKey one. Returns the heap itself.
The method can be used to only decrease or increase the key value of targeted nodes if the binomial heap is either minimum or maximum ordered.
keyNumberCan be any number that corresponds to the key of an existing node.
newKeyNumberNew number value to be used as node key.
const {Heap} = require('binoheap');
// Create a minimum-ordered heap
const minHeap = new Heap((x, y) => x.key - y.key);
minHeap
.insert(10, 'A')
.insert(20, 'B');
//=> Heap {
// size: 2,
// head: Node { key: 10, value: 'A', degree: 1, parent: null, child: [Node], sibling: null } }
minHeap.head;
//=> Node { key: 10, value: 'A', degree: 1, parent: null, child: [Node], sibling: null }
minHeap.head.child;
//=> Node { key: 20, value: 'B', degree: 0, parent: [Node], child: null, sibling: null }
minHeap.updateKey(20, 5);
//=> Heap {
// size: 2,
// head: Node { key: 5, value: 'B', degree: 1, parent: null, child: [Node], sibling: null } }
minHeap.head;
//=> Node { key: 5, value: 'B', degree: 1, parent: null, child: [Node], sibling: null }
minHeap.head.child;
//=> Node { key: 10, value: 'A', degree: 0, parent: [Node], child: null, sibling: null }
// Create a maximum-ordered heap
const maxHeap = new Heap((x, y) => y.key - x.key);
maxHeap
.insert(10, 'A')
.insert(20, 'B');
//=> Heap {
// size: 2,
// head: Node { key: 20, value: 'B', degree: 1, parent: null, child: [Node], sibling: null } }
maxHeap.head;
//=> Node { key: 20, value: 'B', degree: 1, parent: null, child: [Node], sibling: null }
maxHeap.head.child;
//=> Node { key: 10, value: 'A', degree: 0, parent: [Node], child: null, sibling: null }
maxHeap.update(10, 25);
//=> Heap {
// size: 2,
// head: Node { key: 25, value: 'A', degree: 1, parent: null, child: [Node], sibling: null } }
maxHeap.head;
//=> Node { key: 25, value: 'A', degree: 1, parent: null, child: [Node], sibling: null }
maxHeap.head.child;
//=> Node { key: 20, value: 'B', degree: 0, parent: [Node], child: null, sibling: null }
Available, along with the Heap exposed class, is the Node class, mainly useful for testing purposes, since it can be utilized to compare heap nodes. The class has a binary constructor method, with a key and a value parameter, corresponding to the key and the value stored in the created instance, respectively.
keyNumberThe key corresponding to the node instance.
const {Node} = require('binoheap');
const node = new Node(10, 'A');
// => Node { key: 10, value: 'A', degree: 0, parent: null, child: null, sibling: null }
node.key;
//=> 10
valueAnyThe value that the node contains.
const {Node} = require('binoheap');
const node = new Node(10, 'A');
//=> Node { key: 10, value: 'A', degree: 0, parent: null, child: null, sibling: null }
node.value;
//=> 'A'
node.value = 'B'
//=> Node { key: 10, value: 'B', degree: 0, parent: null, child: null, sibling: null }
node.value;
//=> 'B'
degreeNumberDegree of the node.
const {Heap} = require('binoheap');
const heap = new Heap();
//=> Heap {
// size: 0,
// head: null }
heap.insert(10, 'A').head;
//=> Node { key: 10, value: 'A', degree: 0, parent: null, child: null, sibling: null } }
heap.head.degree;
//=> 1
heap.insert(20, 'B').head;
//=> Node { key: 10, value: 'A', degree: 1, parent: null, child: [Node], sibling: null } }
heap.head.degree;
//=> 1
parentNode | nullThe parent node of the node instance.
const {Node} = require('binoheap');
const node1 = new Node(10, 'A');
// => Node { key: 10, value: 'A', degree: 0, parent: null, child: null, sibling: null }
node1.parent;
//=> null
const node2 = new Node(20, 'B');
// => Node { key: 20, value: 'B', degree: 0, parent: null, child: null, sibling: null }
node1.parent = node2;
// => Node { key: 10, value: 'A', degree: 0, parent: [Node], child: null, sibling: null }
childNode | nullThe child node of the node instance.
const {Node} = require('binoheap');
const node1 = new Node(10, 'A');
// => Node { key: 10, value: 'A', degree: 0, parent: null, child: null, sibling: null }
node1.child;
//=> null
const node2 = new Node(20, 'B');
// => Node { key: 20, value: 'B', degree: 0, parent: null, child: null, sibling: null }
node1.child = node2;
// => Node { key: 10, value: 'A', degree: 0, parent: null, child: [Node], sibling: null }
childNode | nullThe sibling node of the node instance.
const {Node} = require('binoheap');
const node1 = new Node(10, 'A');
// => Node { key: 10, value: 'A', degree: 0, parent: null, child: null, sibling: null }
node1.sibling;
//=> null
const node2 = new Node(20, 'B');
// => Node { key: 20, value: 'B', degree: 0, parent: null, child: null, sibling: null }
node1.sibling = node2;
// => Node { key: 10, value: 'A', degree: 0, parent: null, child: null, sibling: [Node] }
siblings()Array<Node>Traverses all sibling nodes of the Node instance and stores them in an array. The array is returned at the end of the traversal.
const {Heap} = require('binoheap');
const heap = new Heap();
//=> Heap {
// size: 0,
// head: null } }
heap
.insert(10, 'A')
.insert(20, 'B')
.insert(30, 'C')
.insert(40, 'D')
.insert(50, 'E')
.insert(60, 'F')
.insert(70, 'G');
//=> Heap {
// size: 7,
// head: Node { key: 70, value: 'G', degree: 0, parent: null, child: [Node], sibling: null } }
heap.head.siblings();
//=> [
// Node { key: 50, value: 'E', degree: 1, parent: null, child: [Node], sibling: [Node] },
// Node { key: 10, value: 'A', degree: 2, parent: null, child: [Node], sibling: null }
// ]
descendants()Array<Node>Traverses all the descendant nodes of the Node instance, through the Node#child pointer, and stores each one of them in an array. The array is returned at the end of the traversal.
const {Heap} = require('binoheap');
const heap = new Heap();
//=> Heap {
// size: 0,
// head: null } }
heap
.insert(10, 'A')
.insert(20, 'B')
.insert(30, 'C')
.insert(40, 'D');
//=> Heap {
// size: 7,
// head: Node { key: 10, value: 'A', degree: 2, parent: null, child: [Node], sibling: null } }
heap.head.descendants();
//=> [
// Node { key: 30, value: 'C', degree: 1, parent: [Node], child: [Node], sibling: [Node] },
// Node { key: 40, value: 'D', degree: 0, parent: [Node], child: , sibling: null }
// ]
toPair()[Number, Any]Returns an ordered-pair/2-tuple, where the first element is a number corresponding to the key of the node, and the last one is a value, that can be of any type, corresponding to the value stored in the node.
const {Heap, Node} = require('binoheap');
const heap = new Heap();
const node = new Node(5, 'B');
node.toPair();
//=> [5, 'B']
heap.insert(10, 'A').head.toPair();
//=> [10, 'A']
For more info on how to contribute to the project, please read the contributing guidelines.
cd binoheapnpm install or yarn installnpm test or yarn testFAQs
Binomial heaps for ES6
We found that binoheap demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Research
Security News
Socket’s threat research team has detected six malicious npm packages typosquatting popular libraries to insert SSH backdoors.
Security News
MITRE's 2024 CWE Top 25 highlights critical software vulnerabilities like XSS, SQL Injection, and CSRF, reflecting shifts due to a refined ranking methodology.
Security News
In this segment of the Risky Business podcast, Feross Aboukhadijeh and Patrick Gray discuss the challenges of tracking malware discovered in open source softare.