Mnemonist
Heap
A Heap is basically a priority queue.
For more information about the Heap, you can head here.
By default, the provided Heap is a min heap and the MaxHeap is just some sugar that will reverse the provided comparator for you.
const Heap = require('mnemonist/heap');
// To access min/max heap
const { MinHeap } = require('mnemonist/heap');
const { MaxHeap } = require('mnemonist/heap');
If you know the maximum number of items you will store and need a more performant implementation, check out the FixedReverseHeap.
Use case
Let’s say we need to schedule tasks having different priorities. A Stack or a Queue might not be enough since we need to be sure at all time that the most urgent tasks will come first.
In such cases, a Heap can help you tremendously by keeping the items you give it ordered following arbitrary logic & preventing you from having to perform costly sort operations on the full list of tasks.
// Let's give a comparator function to our Heap
// to be able to tell which tasks are the most urgent
const heap = new Heap((a, b) => {
if (a.priority > b.priority)
return -1;
if (a.priority < b.priority)
return 1;
return 0;
});
// Let's add some tasks
heap.push({priority: 12, task: 'clean'});
heap.push({priority: 2, task: 'sleep'});
heap.push({priority: 23, task: 'work'});
// Let's peek to see which is the most urgent task
heap.peek().task;
>>> 'work'
// Let's perform our tasks
while (heap.size) {
const task = heap.pop().task;
console.log('Doing:', task);
}
Constructor
The Heap takes a single optional argument being the comparator function to be used to compare the given items.
// Providing a comparator to handle custom objects
const heap = new Heap((a, b) => {
if (a.value < b.value)
return -1;
if (a.value > b.value)
return 1;
return 0;
});
heap.push({value: 34});
heap.push({value: 45});
heap.peek();
>>> 34
Static #.from
Alternatively, one can build a Heap from an arbitrary JavaScript iterable likewise:
const heap = Heap.from([1, 2, 3], comparator);
The construction is done in linear time.
Members
Methods
Mutation
Read
Helpers
If you don’t want to use the Heap class and want to rely on your own array to represent the heap’s data, you can use the helpers below:
If you need to find the n smallest/largest elements from arbitrary iterables efficiently you can use those helpers using heaps under the hood:
#.size
Number of items in the heap.
const heap = new Heap();
heap.size
>>> 0
#.push
Pushes an item into the heap.
O(log n)
const heap = new Heap();
heap.push(34);
#.pop
Retrieve & remove the min item of the heap (or the max item in case of a MaxHeap).
O(log n)
const heap = new Heap();
heap.push(4);
heap.push(34);
heap.push(5);
heap.pop();
>>> 4
heap.size
>>> 2
#.replace
Pop the heap, push an item then return the popped value. It will throw if the heap is empty.
Note that the returned value may be smaller/larger than the given item so be sure to wrap its usage within reasonable conditions!
This is more efficient than doing pop then push and does not change the length of the underlying array.
O(log n)
const heap = new Heap();
heap.push(1);
heap.replace(2);
>>> 1
heap.size
>>> 1
heap.pop();
>>> 2
#.pushpop
Push an item into the heap, then pop the heap. If the heap is empty, the heap will obviously remain empty and you will get your item back.
This is more efficient than doing push than pop and does not change the length of the underlying array.
O(log n)
const heap = new Heap();
heap.push(1);
heap.pushpop(2);
>>> 1
heap.size
>>> 1
heap.pop();
>>> 2
#.consume
Fully consume the heap and return its items as a sorted array.
const heap = new Heap();
heap.push(45);
heap.push(-3);
heap.push(0);
heap.consume();
>>> [-3, 0, 45]
heap.size
>>> 0
#.clear
Completely clears the heap.
const heap = new Heap();
heap.push(34);
heap.clear();
heap.size
>>> 0
#.peek
Retrieves the min item of the heap (or the max item in case of a MaxHeap).
O(1)
const heap = new Heap();
heap.push(4);
heap.push(34);
heap.push(5);
heap.peek();
>>> 4
#.toArray
Converts the heap into an array without altering the heap’s state. Note that the underlying array storing the items is cloned to perform this operation and that you can be more performant if you can consume the heap instead.
This method is mostly used for debugging purposes.
O(n log n)
const heap = new Heap();
heap.push(4);
heap.push(34);
heap.push(5);
heap.toArray();
>>> [4, 5, 34]
heapify
Converts the given array into a heap in linear time.
O(n)
const array = [4, 1, -5, 10];
Heap.heapify(comparator, array);
// You array has been heapified!
push
Push a new item into the heap.
O(log n)
const array = [];
Heap.push(comparator, array, 4);
Heap.push(comparator, array, 3);
Heap.push(comparator, array, 7);
array[0]
>>> 3
pop
Pop the heap.
O(log n)
const array = [];
Heap.push(comparator, array, 4);
Heap.push(comparator, array, 3);
Heap.push(comparator, array, 7);
Heap.pop(comparator, array);
>>> 3
replace
Pop the heap, push an item then return the popped value. It will throw if the heap is empty.
Note that the returned value may be smaller/larger than the given item so be sure to wrap its usage within reasonable conditions!
This is more efficient than doing pop then push and does not change the length of the underlying array.
O(log n)
const array = [];
Heap.push(comparator, array, 1);
Heap.replace(comparator, array, 2);
>>> 1
array.length
>>> 1
Heap.pop(comparator, array);
>>> 2
pushpop
Push an item into the heap, then pop the heap. If the heap is empty, the heap will obviously remain empty and you will get your item back.
This is more efficient than doing push than pop and does not change the length of the underlying array.
O(log n)
const array = [];
Heap.push(comparator, array, 1);
Heap.pushpop(comparator, array, 2);
>>> 1
array.length
>>> 1
Heap.pop(comparator, array);
>>> 2
consume
Completely consumes the heap and returns all its items in a sorted array.
O(n log n)
const array = [4, 1, 3];
Heap.heapify(comparator, array);
Heap.consume(comparator, array);
>>> [1, 3, 4]
array.length
>>> 0
nsmallest
Retrieves the n smallest values from the given iterables.
Runs in O(N log n), N being the total number of values, and n the number of smallest values you want.
Takes up to O(n) space, n being the number of smallest values you want.
Heap.nsmallest(3, [4, 2, 1, 5, 6, 8]);
>>> [1, 2, 4]
// If you need a custom comparator
Heap.nsmallest(comparator, 3, [4, 2, 1, 5, 6, 8]);
nlargest
Retrieves the n largest values from the given iterables.
Runs in O(N log n), N being the total number of values, and n the number of largest values you want.
Takes up to O(n) space, n being the number of largest values you want.
Heap.nlargest(3, [4, 2, 1, 5, 6, 8]);
>>> [8, 6, 5]
// If you need a custom comparator
// BEWARE: must be the same as you would use with nsmallest!
Heap.nlargest(comparator, 3, [4, 2, 1, 5, 6, 8]);