README
@datastructures-js/heap
A javascript implementation for Heap data structure. Heap base class allows creating heaps using a custom comparator, 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
npm install --save @datastructures-js/heap
require
const { Heap, MinHeap, MaxHeap } = require('@datastructures-js/heap');
import
import { Heap, MinHeap, MaxHeap } from '@datastructures-js/heap';
API
constructor
Heap
constructor requires a comparator 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 carComparator = (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>(carComparator);
JS
const carComparator = (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(carComparator);
MinHeap, MaxHeap
constructor does not require a comparator here 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 bidsHeap = new MaxHeap<IBid>((bid: IBid) => bid.value);
JS
const numbersHeap = new MinHeap();
const bidsHeap = new MaxHeap((bid) => bid.value);
insert
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.insert(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
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.extractRoot());
}
/*
-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
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.root()); // -5
console.log(bidsHeap.root()); // { 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 comparator 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*log(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.
TS
const heapifiedCars = Heap.heapify<ICar>(cars, carComparator);
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, carComparator);
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(numbers);
console.log(heapifiedNumbers.isValid()); // true
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(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, carComparator)); // true
console.log(MinHeap.isHeapified<number>(numbers)); // true
console.log(MaxHeap.isHeapified<IBid>(bids, (bid) => bid.value)); // true
JS
console.log(Heap.isHeapified(cars, carComparator)); // true
console.log(MinHeap.isHeapified(numbers)); // true
console.log(MaxHeap.isHeapified(bids, (bid) => bid.value)); // true
Build
grunt build
License
The MIT License. Full License is here