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.

var Heap = require('mnemonist/heap');

// To access min/max heap
var MinHeap = require('mnemonist/heap').MinHeap;
var MaxHeap = require('mnemonist/heap').MaxHeap;

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
var heap = new Heap(function(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) {
  var 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
var heap = new Heap(function(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:

var 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.

var heap = new Heap();
heap.size
>>> 0

#.push

Pushes an item into the heap.

O(log n)

var 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)

var 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)

var 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)

var 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.

var 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.

var 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)

var 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)

var 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)

var 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)

var 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)

var 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)

var 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)

var 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)

var 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(3, comparator, [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(3, comparator, [4, 2, 1, 5, 6, 8]);