@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
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) {
return 1;
}
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) {
return 1;
}
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));
removes and returns the root (top) value of the heap in O(log(n)) runtime.
while (!carsHeap.isEmpty()) {
console.log(carsHeap.extractRoot());
}
while (!numbersHeap.isEmpty()) {
console.log(numbersHeap.pop());
}
while (!bidsHeap.isEmpty()) {
console.log(bidsHeap.extractRoot());
}
root (top)
returns the root node without removing it.
cars.forEach((car) => carsHeap.insert(car));
numbers.forEach((num) => numbersHeap.insert(num));
bids.forEach((bid) => bidsHeap.insert(bid));
console.log(carsHeap.root());
console.log(numbersHeap.top());
console.log(bidsHeap.top());
leaf
returns a leaf node in the heap.
console.log(carsHeap.leaf());
console.log(numbersHeap.leaft());
console.log(bidsHeap.leaf());
size
returns the number of nodes in the heap.
console.log(carsHeap.size());
console.log(numbersHeap.size());
console.log(bidsHeap.size());
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());
console.log(numbersHeap.sort());
console.log(bidsHeap.sort());
isValid
checks if the heap is valid (all nodes are positioned correctly) in log(n) runtime.
console.log(carsHeap.isValid());
console.log(numbersHeap.isValid());
console.log(bidsHeap.isValid());
fix
fixes the heap by making the necessary swaps between nodes in O(n) runtime.
console.log(carsHeap.fix().isValid());
console.log(numbersHeap.fix().isValid());
console.log(bidsHeap.fix().isValid());
clone
creates a shallow copy of the heap.
console.log(carsHeap.clone().sort());
console.log(numbersHeap.clone().sort());
console.log(bidsHeap.clone().sort());
console.log(carsHeap.isValid());
console.log(numbersHeap.isValid());
console.log(bidsHeap.isValid());
clear
clears the heap.
carsHeap.clear();
numbersHeap.clear();
bidsHeap.clear();
console.log(carsHeap.size());
console.log(numbersHeap.size());
console.log(bidsHeap.size());
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());
console.log(cars);
const heapifiedNumbers = MinHeap.heapify<number>(numbers);
console.log(heapifiedNumbers.isValid());
console.log(numbers);
const heapifiedBids = MaxHeap.heapify<IBid>(bids, (bid) => bid.value);
console.log(heapifiedBids.isValid());
console.log(bids);
JS
const heapifiedCars = Heap.heapify(cars, compareCars);
console.log(heapifiedCars.isValid());
console.log(heapifiedCars.leaf());
console.log(cars);
const heapifiedNumbers = MinHeap.heapify(numbers);
console.log(heapifiedNumbers.isValid());
console.log(heapifiedNumbers.leaf());
console.log(numbers);
const heapifiedBids = MaxHeap.heapify(bids, (bid) => bid.value);
console.log(heapifiedBids.isValid());
console.log(heapifiedBids.leaf());
console.log(bids);
isHeapified
Checks if a given list is heapified.
TS
console.log(Heap.isHeapified<ICar>(cars, compareCars));
console.log(MinHeap.isHeapified<number>(numbers));
console.log(MaxHeap.isHeapified<IBid>(bids, (bid) => bid.value));
JS
console.log(Heap.isHeapified(cars, compareCars));
console.log(MinHeap.isHeapified(numbers));
console.log(MaxHeap.isHeapified(bids, (bid) => bid.value));
Symbol.iterator
The heaps implement a Symbol.iterator that makes them iterable on pop
.
console.log([...carsHeap]);
console.log(carsHeap.size());
console.log([...numbersHeap]);
console.log(numbersHeap.size());
for (const bid of bidsHeap) {
console.log(bid);
}
console.log(bidsHeap.size());
Build
grunt build
License
The MIT License. Full License is here