@datastructures-js/heap

A javascript implementation for Heap data structure. Heap base class allows creating heaps using a custom compare function, and MinHeap/MaxHeap classes extend it for use cases that do not require complex comparison like primitive values and known comparison object prop.

contents

• Install
• require
• import
• API
  • constructor
  • insert (push)
  • extractRoot (pop)
  • root (top)
  • leaf
  • size
  • sort
  • isValid
  • fix
  • clone
  • clear
  • heapify
  • isHeapified
  • Symbol.iterator
  • toArray
• Build
• License

install

1npm install --save @datastructures-js/heap

require

1const { Heap, MinHeap, MaxHeap } = require('@datastructures-js/heap');

import

1import {
2  Heap,
3  MinHeap,
4  MaxHeap,
5  ICompare,
6  IGetCompareValue,
7} from '@datastructures-js/heap';

API

constructor

Heap

constructor requires a compare function that tells the heap when to swap values. Function works similar to javascript sort callback, bigger than 0, means, swap elements.

TS

1interface ICar {
2  year: number;
3  price: number;
4}
5
6const compareCars: ICompare<ICar> = (a: ICar, b: ICar) => {
7  if (a.year > b.year) {
8    return -1;
9  }
10  if (a.year < b.year) {
11    // prioratize newest cars
12    return 1;
13  }
14  // with least price
15  return a.price < b.price ? -1 : 1;
16};
17
18const carsHeap = new Heap<ICar>(compareCars);

JS

1const compareCars = (a, b) => {
2  if (a.year > b.year) {
3    return -1;
4  }
5  if (a.year < b.year) {
6    // prioratize newest cars
7    return 1;
8  }
9  // with least price
10  return a.price < b.price ? -1 : 1;
11};
12
13const carsHeap = new Heap(compareCars);

MinHeap, MaxHeap

constructor does not require a compare function and it's useful when working with primitive values like numbers, it can also be used with objects by passing a callback that indicates what object prop will be used in comparison.

TS

1const numbersHeap = new MinHeap<number>();
2
3interface IBid {
4  id: number;
5  value: number;
6}
7const getBidCompareValue: IGetCompareValue<IBid> = (bid: IBid) => bid.value;
8const bidsHeap = new MaxHeap<IBid>(getBidCompareValue);

JS

1const numbersHeap = new MinHeap();
2const bidsHeap = new MaxHeap((bid) => bid.value);

insert (push)

inserts a value in a correct position into the heap in O(log(n)) runtime.

1const cars = [
2  { year: 2013, price: 35000 },
3  { year: 2010, price: 2000 },
4  { year: 2013, price: 30000 },
5  { year: 2017, price: 50000 },
6  { year: 2013, price: 25000 },
7  { year: 2015, price: 40000 },
8  { year: 2022, price: 70000 }
9];
10cars.forEach((car) => carsHeap.insert(car));
11
12const numbers = [3, -2, 5, 0, -1, -5, 4];
13numbers.forEach((num) => numbersHeap.push(num));
14
15const bids = [
16  { id: 1, value: 1000 },
17  { id: 2, value: 20000 },
18  { id: 3, value: 1000 },
19  { id: 4, value: 1500 },
20  { id: 5, value: 12000 },
21  { id: 6, value: 4000 },
22  { id: 7, value: 8000 }
23];
24bids.forEach((bid) => bidsHeap.insert(bid));

extractRoot (pop)

removes and returns the root (top) value of the heap in O(log(n)) runtime.

1while (!carsHeap.isEmpty()) {
2  console.log(carsHeap.extractRoot());
3}
4/*
5{ year: 2022, price: 70000 }
6{ year: 2017, price: 50000 }
7{ year: 2015, price: 40000 }
8{ year: 2013, price: 25000 }
9{ year: 2013, price: 30000 }
10{ year: 2013, price: 35000 }
11{ year: 2010, price: 2000 }
12*/
13
14while (!numbersHeap.isEmpty()) {
15  console.log(numbersHeap.pop());
16}
17/*
18-5
19-2
20-1
210
223
234
245
25*/
26
27while (!bidsHeap.isEmpty()) {
28  console.log(bidsHeap.extractRoot());
29}
30/*
31{ id: 2, value: 20000 }
32{ id: 5, value: 12000 }
33{ id: 7, value: 8000 }
34{ id: 6, value: 4000 }
35{ id: 4, value: 1500 }
36{ id: 3, value: 1000 }
37{ id: 1, value: 1000 }
38*/

root (top)

returns the root node without removing it.

1// reload values
2cars.forEach((car) => carsHeap.insert(car));
3numbers.forEach((num) => numbersHeap.insert(num));
4bids.forEach((bid) => bidsHeap.insert(bid));
5
6console.log(carsHeap.root()); // { year: 2022, price: 70000 }
7console.log(numbersHeap.top()); // -5
8console.log(bidsHeap.top()); // { id: 2, value: 20000 }

leaf

returns a leaf node in the heap.

1console.log(carsHeap.leaf()); // { year: 2010, price: 2000 }
2console.log(numbersHeap.leaft()); // 5
3console.log(bidsHeap.leaf()); // { id: 1, value: 1000 }

size

returns the number of nodes in the heap.

1console.log(carsHeap.size()); // 7
2console.log(numbersHeap.size()); // 7
3console.log(bidsHeap.size()); // 7

sort

returns a list of sorted values in O(n*log(n)) runtime, based on the comparison logic, and in reverse order. In MaxHeap it returns the list of sorted values in ascending order, and in descending order in MinHeap. sort mutates the node positions in the heap, to prevent that, you can sort a clone of the heap.

1console.log(carsHeap.sort());
2/*
3[
4  { year: 2010, price: 2000 },
5  { year: 2013, price: 35000 },
6  { year: 2013, price: 30000 },
7  { year: 2013, price: 25000 },
8  { year: 2015, price: 40000 },
9  { year: 2017, price: 50000 },
10  { year: 2022, price: 70000 }
11]
12*/
13
14console.log(numbersHeap.sort());
15// [5, 4, 3, 0, -1, -2, -5]
16
17console.log(bidsHeap.sort());
18/*
19[
20  { id: 1, value: 1000 },
21  { id: 3, value: 1000 },
22  { id: 4, value: 1500 },
23  { id: 6, value: 4000 },
24  { id: 7, value: 8000 },
25  { id: 5, value: 12000 },
26  { id: 2, value: 20000 }
27]
28*/

isValid

checks if the heap is valid (all nodes are positioned correctly) in log(n) runtime.

1// after sorting the heaps directly, node positions are mutated
2console.log(carsHeap.isValid()); // false
3console.log(numbersHeap.isValid()); // false
4console.log(bidsHeap.isValid()); // false

fix

fixes the heap by making the necessary swaps between nodes in O(n) runtime.

1console.log(carsHeap.fix().isValid()); // true
2
3console.log(numbersHeap.fix().isValid()); // true
4
5console.log(bidsHeap.fix().isValid()); // true

clone

creates a shallow copy of the heap.

1console.log(carsHeap.clone().sort());
2/*
3[
4  { year: 2010, price: 2000 },
5  { year: 2013, price: 35000 },
6  { year: 2013, price: 30000 },
7  { year: 2013, price: 25000 },
8  { year: 2015, price: 40000 },
9  { year: 2017, price: 50000 },
10  { year: 2022, price: 70000 }
11]
12*/
13
14console.log(numbersHeap.clone().sort());
15// [5, 4, 3, 0, -1, -2, -5]
16
17console.log(bidsHeap.clone().sort());
18/*
19[
20  { id: 1, value: 1000 },
21  { id: 3, value: 1000 },
22  { id: 4, value: 1500 },
23  { id: 6, value: 4000 },
24  { id: 7, value: 8000 },
25  { id: 5, value: 12000 },
26  { id: 2, value: 20000 }
27]
28*/
29
30// original heaps not mutated
31console.log(carsHeap.isValid()); // true
32console.log(numbersHeap.isValid()); // true
33console.log(bidsHeap.isValid()); // true

clear

clears the heap.

1carsHeap.clear();
2numbersHeap.clear();
3bidsHeap.clear();
4
5console.log(carsHeap.size()); // 0
6console.log(numbersHeap.size()); // 0
7console.log(bidsHeap.size()); // 0

heapify

converts a list of values into a heap without using an additional space in O(n) runtime.

TS

1const heapifiedCars = Heap.heapify<ICar>(cars, compareCars);
2console.log(heapifiedCars.isValid()); // true
3// list is heapified
4console.log(cars);
5/*
6[
7  { year: 2022, price: 70000 },
8  { year: 2013, price: 25000 },
9  { year: 2017, price: 50000 },
10  { year: 2010, price: 2000 },
11  { year: 2013, price: 30000 },
12  { year: 2013, price: 35000 },
13  { year: 2015, price: 40000 }
14]
15*/
16
17const heapifiedNumbers = MinHeap.heapify<number>(numbers);
18console.log(heapifiedNumbers.isValid()); // true
19console.log(numbers);
20// [-5, -1, -2, 3, 0, 5, 4]
21
22const heapifiedBids = MaxHeap.heapify<IBid>(bids, (bid) => bid.value);
23console.log(heapifiedBids.isValid()); // true
24console.log(bids);
25/*
26[
27  { id: 2, value: 20000 },
28  { id: 5, value: 12000 },
29  { id: 7, value: 8000 },
30  { id: 1, value: 1000 },
31  { id: 4, value: 1500 },
32  { id: 3, value: 1000 },
33  { id: 6, value: 4000 }
34]
35*/

JS

1const heapifiedCars = Heap.heapify(cars, compareCars);
2console.log(heapifiedCars.isValid()); // true
3console.log(heapifiedCars.leaf()); // { year: 2010, price: 2000 }
4
5// original list is heapified
6console.log(cars);
7/*
8[
9  { year: 2022, price: 70000 },
10  { year: 2013, price: 25000 },
11  { year: 2017, price: 50000 },
12  { year: 2010, price: 2000 },
13  { year: 2013, price: 30000 },
14  { year: 2013, price: 35000 },
15  { year: 2015, price: 40000 }
16]
17*/
18
19const heapifiedNumbers = MinHeap.heapify(numbers);
20console.log(heapifiedNumbers.isValid()); // true
21console.log(heapifiedNumbers.leaf()); // 5
22console.log(numbers);
23// [-5, -1, -2, 3, 0, 5, 4]
24
25const heapifiedBids = MaxHeap.heapify(bids, (bid) => bid.value);
26console.log(heapifiedBids.isValid()); // true
27console.log(heapifiedBids.leaf()); // { id: 1, value: 1000 }
28console.log(bids);
29/*
30[
31  { id: 2, value: 20000 },
32  { id: 5, value: 12000 },
33  { id: 7, value: 8000 },
34  { id: 1, value: 1000 },
35  { id: 4, value: 1500 },
36  { id: 3, value: 1000 },
37  { id: 6, value: 4000 }
38]
39*/

isHeapified

Checks if a given list is heapified.

TS

1console.log(Heap.isHeapified<ICar>(cars, compareCars)); // true
2console.log(MinHeap.isHeapified<number>(numbers)); // true
3console.log(MaxHeap.isHeapified<IBid>(bids, (bid) => bid.value)); // true

JS

1console.log(Heap.isHeapified(cars, compareCars)); // true
2console.log(MinHeap.isHeapified(numbers)); // true
3console.log(MaxHeap.isHeapified(bids, (bid) => bid.value)); // true

Symbol.iterator

The heaps implement a Symbol.iterator that makes them iterable on pop.

1console.log([...carsHeap]);
2/*
3[
4  { year: 2022, price: 70000 },
5  { year: 2017, price: 50000 },
6  { year: 2015, price: 40000 },
7  { year: 2013, price: 25000 },
8  { year: 2013, price: 30000 },
9  { year: 2013, price: 35000 },
10  { year: 2010, price: 2000 }
11]
12*/
13console.log(carsHeap.size()); // 0
14
15console.log([...numbersHeap]); // [5, -5, -2, -1, 0, 3, 4]
16console.log(numbersHeap.size()); // 0
17
18for (const bid of bidsHeap) {
19  console.log(bid);
20}
21/*
22{ id: 2, value: 20000 }
23{ id: 5, value: 12000 }
24{ id: 7, value: 8000 }
25{ id: 6, value: 4000 }
26{ id: 4, value: 1500 }
27{ id: 1, value: 1000 }
28{ id: 3, value: 1000 }
29*/
30console.log(bidsHeap.size()); // 0

toArray

Converts the heap to a cloned array without sorting.

1console.log(carsHeap.toArray());
2/*
3[
4  { year: 2022, price: 70000 },
5  { year: 2017, price: 50000 },
6  { year: 2015, price: 40000 },
7  { year: 2013, price: 25000 },
8  { year: 2013, price: 30000 },
9  { year: 2013, price: 35000 },
10  { year: 2010, price: 2000 }
11]
12*/
13
14
15console.log(numbersHeap.toArray()); // [5, -5, -2, -1, 0, 3, 4]
16
17console.log(bidsHeap.toArray());
18
19/*
20[
21{ id: 2, value: 20000 },
22{ id: 5, value: 12000 },
23{ id: 7, value: 8000 },
24{ id: 6, value: 4000 },
25{ id: 4, value: 1500 },
26{ id: 1, value: 1000 },
27{ id: 3, value: 1000 }
28]
29*/
30

Build

grunt build

License

The MIT License. Full License is here