@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

npm install --save @datastructures-js/heap

require

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

import

import {
  Heap,
  MinHeap,
  MaxHeap,
  ICompare,
  IGetCompareValue,
} 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

interface ICar {
  year: number;
  price: number;
}

const compareCars: ICompare<ICar> = (a: ICar, b: ICar) => {
  if (a.year > b.year) {
    return -1;
  }
  if (a.year < b.year) {
    // prioratize newest cars
    return 1;
  }
  // with least price
  return a.price < b.price ? -1 : 1;
};

const carsHeap = new Heap<ICar>(compareCars);

JS

const compareCars = (a, b) => {
  if (a.year > b.year) {
    return -1;
  }
  if (a.year < b.year) {
    // prioratize newest cars
    return 1;
  }
  // with least price
  return a.price < b.price ? -1 : 1;
};

const 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

const numbersHeap = new MinHeap<number>();

interface IBid {
  id: number;
  value: number;
}
const getBidCompareValue: IGetCompareValue<IBid> = (bid: IBid) => bid.value;
const bidsHeap = new MaxHeap<IBid>(getBidCompareValue);

JS

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

insert (push)

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

const cars = [
  { year: 2013, price: 35000 },
  { year: 2010, price: 2000 },
  { year: 2013, price: 30000 },
  { year: 2017, price: 50000 },
  { year: 2013, price: 25000 },
  { year: 2015, price: 40000 },
  { year: 2022, price: 70000 }
];
cars.forEach((car) => carsHeap.insert(car));

const numbers = [3, -2, 5, 0, -1, -5, 4];
numbers.forEach((num) => numbersHeap.push(num));

const bids = [
  { id: 1, value: 1000 },
  { id: 2, value: 20000 },
  { id: 3, value: 1000 },
  { id: 4, value: 1500 },
  { id: 5, value: 12000 },
  { id: 6, value: 4000 },
  { id: 7, value: 8000 }
];
bids.forEach((bid) => bidsHeap.insert(bid));

extractRoot (pop)

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

while (!carsHeap.isEmpty()) {
  console.log(carsHeap.extractRoot());
}
/*
{ year: 2022, price: 70000 }
{ year: 2017, price: 50000 }
{ year: 2015, price: 40000 }
{ year: 2013, price: 25000 }
{ year: 2013, price: 30000 }
{ year: 2013, price: 35000 }
{ year: 2010, price: 2000 }
*/

while (!numbersHeap.isEmpty()) {
  console.log(numbersHeap.pop());
}
/*
-5
-2
-1
0
3
4
5
*/

while (!bidsHeap.isEmpty()) {
  console.log(bidsHeap.extractRoot());
}
/*
{ id: 2, value: 20000 }
{ id: 5, value: 12000 }
{ id: 7, value: 8000 }
{ id: 6, value: 4000 }
{ id: 4, value: 1500 }
{ id: 3, value: 1000 }
{ id: 1, value: 1000 }
*/

root (top)

returns the root node without removing it.

// reload values
cars.forEach((car) => carsHeap.insert(car));
numbers.forEach((num) => numbersHeap.insert(num));
bids.forEach((bid) => bidsHeap.insert(bid));

console.log(carsHeap.root()); // { year: 2022, price: 70000 }
console.log(numbersHeap.top()); // -5
console.log(bidsHeap.top()); // { id: 2, value: 20000 }

leaf

returns a leaf node in the heap.

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

size

returns the number of nodes in the heap.

console.log(carsHeap.size()); // 7
console.log(numbersHeap.size()); // 7
console.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.

console.log(carsHeap.sort());
/*
[
  { year: 2010, price: 2000 },
  { year: 2013, price: 35000 },
  { year: 2013, price: 30000 },
  { year: 2013, price: 25000 },
  { year: 2015, price: 40000 },
  { year: 2017, price: 50000 },
  { year: 2022, price: 70000 }
]
*/

console.log(numbersHeap.sort());
// [5, 4, 3, 0, -1, -2, -5]

console.log(bidsHeap.sort());
/*
[
  { id: 1, value: 1000 },
  { id: 3, value: 1000 },
  { id: 4, value: 1500 },
  { id: 6, value: 4000 },
  { id: 7, value: 8000 },
  { id: 5, value: 12000 },
  { id: 2, value: 20000 }
]
*/

isValid

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

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

fix

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

console.log(carsHeap.fix().isValid()); // true

console.log(numbersHeap.fix().isValid()); // true

console.log(bidsHeap.fix().isValid()); // true

clone

creates a shallow copy of the heap.

console.log(carsHeap.clone().sort());
/*
[
  { year: 2010, price: 2000 },
  { year: 2013, price: 35000 },
  { year: 2013, price: 30000 },
  { year: 2013, price: 25000 },
  { year: 2015, price: 40000 },
  { year: 2017, price: 50000 },
  { year: 2022, price: 70000 }
]
*/

console.log(numbersHeap.clone().sort());
// [5, 4, 3, 0, -1, -2, -5]

console.log(bidsHeap.clone().sort());
/*
[
  { id: 1, value: 1000 },
  { id: 3, value: 1000 },
  { id: 4, value: 1500 },
  { id: 6, value: 4000 },
  { id: 7, value: 8000 },
  { id: 5, value: 12000 },
  { id: 2, value: 20000 }
]
*/

// original heaps not mutated
console.log(carsHeap.isValid()); // true
console.log(numbersHeap.isValid()); // true
console.log(bidsHeap.isValid()); // true

clear

clears the heap.

carsHeap.clear();
numbersHeap.clear();
bidsHeap.clear();

console.log(carsHeap.size()); // 0
console.log(numbersHeap.size()); // 0
console.log(bidsHeap.size()); // 0

heapify

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

TS

const heapifiedCars = Heap.heapify<ICar>(cars, compareCars);
console.log(heapifiedCars.isValid()); // true
// list is heapified
console.log(cars);
/*
[
  { year: 2022, price: 70000 },
  { year: 2013, price: 25000 },
  { year: 2017, price: 50000 },
  { year: 2010, price: 2000 },
  { year: 2013, price: 30000 },
  { year: 2013, price: 35000 },
  { year: 2015, price: 40000 }
]
*/

const heapifiedNumbers = MinHeap.heapify<number>(numbers);
console.log(heapifiedNumbers.isValid()); // true
console.log(numbers);
// [-5, -1, -2, 3, 0, 5, 4]

const heapifiedBids = MaxHeap.heapify<IBid>(bids, (bid) => bid.value);
console.log(heapifiedBids.isValid()); // true
console.log(bids);
/*
[
  { id: 2, value: 20000 },
  { id: 5, value: 12000 },
  { id: 7, value: 8000 },
  { id: 1, value: 1000 },
  { id: 4, value: 1500 },
  { id: 3, value: 1000 },
  { id: 6, value: 4000 }
]
*/

JS

const heapifiedCars = Heap.heapify(cars, compareCars);
console.log(heapifiedCars.isValid()); // true
console.log(heapifiedCars.leaf()); // { year: 2010, price: 2000 }

// original list is heapified
console.log(cars);
/*
[
  { year: 2022, price: 70000 },
  { year: 2013, price: 25000 },
  { year: 2017, price: 50000 },
  { year: 2010, price: 2000 },
  { year: 2013, price: 30000 },
  { year: 2013, price: 35000 },
  { year: 2015, price: 40000 }
]
*/

const heapifiedNumbers = MinHeap.heapify(numbers);
console.log(heapifiedNumbers.isValid()); // true
console.log(heapifiedNumbers.leaf()); // 5
console.log(numbers);
// [-5, -1, -2, 3, 0, 5, 4]

const heapifiedBids = MaxHeap.heapify(bids, (bid) => bid.value);
console.log(heapifiedBids.isValid()); // true
console.log(heapifiedBids.leaf()); // { id: 1, value: 1000 }
console.log(bids);
/*
[
  { id: 2, value: 20000 },
  { id: 5, value: 12000 },
  { id: 7, value: 8000 },
  { id: 1, value: 1000 },
  { id: 4, value: 1500 },
  { id: 3, value: 1000 },
  { id: 6, value: 4000 }
]
*/

isHeapified

Checks if a given list is heapified.

TS

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

JS

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

Symbol.iterator

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

console.log([...carsHeap]);
/*
[
  { year: 2022, price: 70000 },
  { year: 2017, price: 50000 },
  { year: 2015, price: 40000 },
  { year: 2013, price: 25000 },
  { year: 2013, price: 30000 },
  { year: 2013, price: 35000 },
  { year: 2010, price: 2000 }
]
*/
console.log(carsHeap.size()); // 0

console.log([...numbersHeap]); // [5, -5, -2, -1, 0, 3, 4]
console.log(numbersHeap.size()); // 0

for (const bid of bidsHeap) {
  console.log(bid);
}
/*
{ id: 2, value: 20000 }
{ id: 5, value: 12000 }
{ id: 7, value: 8000 }
{ id: 6, value: 4000 }
{ id: 4, value: 1500 }
{ id: 1, value: 1000 }
{ id: 3, value: 1000 }
*/
console.log(bidsHeap.size()); // 0

toArray

Converts the heap to a cloned array without sorting.

console.log(carsHeap.toArray());
/*
[
  { year: 2022, price: 70000 },
  { year: 2017, price: 50000 },
  { year: 2015, price: 40000 },
  { year: 2013, price: 25000 },
  { year: 2013, price: 30000 },
  { year: 2013, price: 35000 },
  { year: 2010, price: 2000 }
]
*/


console.log(numbersHeap.toArray()); // [5, -5, -2, -1, 0, 3, 4]

console.log(bidsHeap.toArray());

/*
[
{ id: 2, value: 20000 },
{ id: 5, value: 12000 },
{ id: 7, value: 8000 },
{ id: 6, value: 4000 },
{ id: 4, value: 1500 },
{ id: 1, value: 1000 },
{ id: 3, value: 1000 }
]
*/

Build

grunt build

License

The MIT License. Full License is here

Changelog

All notable changes to this project will be documented in this file.

The format is based on Keep a Changelog, and this project adheres to Semantic Versioning.

[Unreleased]

[4.3.3] - 2024-01-07

Fixed

• default compare function for MinHeap

[4.3.2] - 2023-06-19

Fixed

• ts types.

[4.3.1] - 2023-01-08

Fixed

• lint config.

[4.3.0] - 2023-01-08

Added

• toArray to convert the heap into an array without sorting.

[4.2.2] - 2022-12-24

Fixed

• add iterable for ts definitions.

[4.2.1] - 2022-12-23

Fixed

• typo in readme.

[4.2.0] - 2022-12-23

Added

• Symbol.iterator to iterate on heaps pop.

Fixed

• .fix() to also fix heap leaf value in addition to nodes positions.

[4.1.2] - 2022-09-04

Fixed

• Optimize .fix() to run in O(n) runtime instead of O(n*log(n)).

[4.1.1] - 2022-08-15

Fixed

• add types to package.json

[4.1.0] - 2022-05-30

Added

• push, pop & top as alias methods for insert, extractRoot & root

[4.0.2] - 2022-03-13

Fixed

• ts types (again).

[4.0.1] - 2022-03-09

Fixed

• ts types.

[4.0.0] - 2022-02-21

Changed

• better code, better world.

[3.2.0] - 2021-08-05

Added

• CustomHeap to allow constructing a heap with a custom comparator callback.

[3.1.1] - 2021-06-20

Fixed

• index.d.ts

[3.1.0] - 2021-06-15

Added

• typescript.

[3.0.1] - 2021-03-28

Fixed

• Readme

[3.0.0] - 2020-01-17

Changed

• simplified heap nodes. preserves numbers and strings, and use object literal for key:value.
• .heapify static function now heapify the input list as well as returning a heap insatnce.

Added

• .fix() to fix positions of nodes in the heap.
• .isValid to validate heap nodes are in right positions.
• .isHeapified static function to valida if a given list is heapified.

Fixed

• jsdoc
• README

[2.0.0] - 2020-04-06

Changed

• remove none-standard method .serialize().

Fixed

• return inserted node in Min/Max Heap.
• README
• jsdoc

[1.2.0] - 2020-03-07

Added

• .leaf() to get the max node in a MinHeap or the min node in a MaxHeap.

[1.1.2] - 2020-03-06

Fixed

• params naming.

[1.1.1] - 2019-12-24

Fixed

• add a table of content to readme

[1.1.0] - 2019-12-16

Added

.serialize() to convert a heap to a list of serialized nodes.

Fixed

• improve README.

[1.0.1] - 2019-12-16

Fixed

• Readme & Description.

[1.0.0] - 2019-12-15

Added

• initial release