@datastructures-js/heap
Advanced tools
@datastructures-js/heap is an npm package that provides implementations of heap data structures, including MinHeap and MaxHeap. These data structures are useful for efficiently managing and retrieving the minimum or maximum element in a collection, which is particularly useful in algorithms like priority queues, Dijkstra's algorithm, and more.
MinHeap
The MinHeap feature allows you to create a heap where the smallest element is always at the root. This is useful for scenarios where you need to efficiently retrieve the minimum element.
const { MinHeap } = require('@datastructures-js/heap');
const minHeap = new MinHeap();
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(8);
console.log(minHeap.extractRoot()); // 3
console.log(minHeap.root()); // 5MaxHeap
The MaxHeap feature allows you to create a heap where the largest element is always at the root. This is useful for scenarios where you need to efficiently retrieve the maximum element.
const { MaxHeap } = require('@datastructures-js/heap');
const maxHeap = new MaxHeap();
maxHeap.insert(5);
maxHeap.insert(3);
maxHeap.insert(8);
console.log(maxHeap.extractRoot()); // 8
console.log(maxHeap.root()); // 5Heapify an Array
The heapify feature allows you to convert an existing array into a heap. This is useful for initializing a heap with a predefined set of elements.
const { MinHeap } = require('@datastructures-js/heap');
const array = [5, 3, 8, 1, 2];
const minHeap = MinHeap.heapify(array);
console.log(minHeap.root()); // 1Heap Sort
Heap sort is a sorting algorithm that uses a heap to sort elements. This feature demonstrates how to use a MinHeap to sort an array in ascending order.
const { MinHeap } = require('@datastructures-js/heap');
const array = [5, 3, 8, 1, 2];
const minHeap = MinHeap.heapify(array);
const sortedArray = [];
while (!minHeap.isEmpty()) {
sortedArray.push(minHeap.extractRoot());
}
console.log(sortedArray); // [1, 2, 3, 5, 8]heap-js is another npm package that provides heap data structures. It supports both MinHeap and MaxHeap and offers similar functionalities to @datastructures-js/heap. One key difference is that heap-js provides additional customization options for the comparator function, allowing for more flexible heap implementations.
js-priority-queue is a package that implements a priority queue using a binary heap. It offers similar functionalities to @datastructures-js/heap but focuses more on the priority queue aspect. It provides a simple API for managing elements with priorities, making it a good choice for applications that require priority-based element retrieval.
heap is a minimalistic package that provides a binary heap implementation. It supports both MinHeap and MaxHeap and offers basic heap operations. Compared to @datastructures-js/heap, it has a smaller feature set but is lightweight and easy to use for simple heap operations.
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.
npm install --save @datastructures-js/heap
const { Heap, MinHeap, MaxHeap } = require('@datastructures-js/heap');
import {
Heap,
MinHeap,
MaxHeap,
ICompare,
IGetCompareValue,
} from '@datastructures-js/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.
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);
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);
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.
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);
const numbersHeap = new MinHeap();
const bidsHeap = new MaxHeap((bid) => bid.value);
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());
}
/*
{ 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 }
*/
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 }
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 }
returns the number of nodes in the heap.
console.log(carsHeap.size()); // 7
console.log(numbersHeap.size()); // 7
console.log(bidsHeap.size()); // 7
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 }
]
*/
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
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
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
clears the heap.
carsHeap.clear();
numbersHeap.clear();
bidsHeap.clear();
console.log(carsHeap.size()); // 0
console.log(numbersHeap.size()); // 0
console.log(bidsHeap.size()); // 0
converts a list of values into a heap without using an additional space in O(n) runtime.
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 }
]
*/
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 }
]
*/
Checks if a given list is heapified.
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
console.log(Heap.isHeapified(cars, compareCars)); // true
console.log(MinHeap.isHeapified(numbers)); // true
console.log(MaxHeap.isHeapified(bids, (bid) => bid.value)); // true
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
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 }
]
*/
grunt build
The MIT License. Full License is here
[4.3.3] - 2024-01-07
FAQs
Min/Max Heap & Heap Sort implementation in javascript
We found that @datastructures-js/heap demonstrated a healthy version release cadence and project activity because the last version was released less than a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Research
Security News
Socket researchers uncover a malicious npm package posing as a tool for detecting vulnerabilities in Etherium smart contracts.
Security News
Research
A supply chain attack on Rspack's npm packages injected cryptomining malware, potentially impacting thousands of developers.
Research
Security News
Socket researchers discovered a malware campaign on npm delivering the Skuld infostealer via typosquatted packages, exposing sensitive data.