@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 Sort algorithm.
| Min Heap | Max Heap |
|---|---|
|
|
npm install --save @datastructures-js/heap
const { MinHeap, MaxHeap, CustomHeap } = require('@datastructures-js/heap');
import { MinHeap, MaxHeap, CustomHeap, HeapNode } from '@datastructures-js/heap';
// HeapNode is the key/value interface for MinHeap/MaxHeap
creates an empty heap. use CustomHeap when you need advanced comparison logic between heap nodes. For primitive comparisons, use MinHeap/MaxHeap.
const minHeap = new MinHeap();
const maxHeap = new MaxHeap();
// comparator receievs the parent (a) and child (b) in each comparison
// and should return a number, if bigger than 0, it will swap nodes.
const customMinHeap = new CustomHeap((a, b) => a.count - b.count);
const customMaxHeap = new CustomHeap((a, b) => a.name < b.name ? 1 : -1);
const minHeap = new MinHeap<number, [number, number]>();
const maxHeap = new MaxHeap<string, { name: string }>();
// comparator receievs the parent (a) and child (b) in each comparison
// and should return a number, if bigger than 0, it will swap nodes.
const customMinHeap = new CustomHeap<{ count: number }>(
(a, b) => a.count - b.count
);
const customMaxHeap = new CustomHeap<{ name: string }>(
(a, b) => a.name < b.name ? 1 : -1
);
insert a node into the heap. If value is provided (anything except undefined), the node is stored as {key: ..., value: ...} otherwise, the node is the key (number or string). For CustomHeap, anything can be inserted as a comparator is provided to compare nodes.
| params | return | runtime |
|---|---|---|
|
key: T (number | string)
value: U (any) | MinHeap<T, U> | MaxHeap<T, U> | O(log(n)) |
minHeap
.insert(50)
.insert(80)
.insert(30, 'something')
.insert(90)
.insert(60, null)
.insert(40)
.insert(20, { name: 'test' });
maxHeap
.insert('m')
.insert('x')
.insert('f', 'something')
.insert('b')
.insert('z', null)
.insert('k')
.insert('c', { name: 'test' });
| params | return | runtime |
|---|---|---|
| key: T | CustomHeap<T> | O(log(n)) |
customMaxHeap
.insert({ name: 'm' })
.insert({ name: 'x' })
.insert({ name: 'f' })
.insert({ name: 'b' })
.insert({ name: 'z' })
.insert({ name: 'k' })
.insert({ name: 'c' });
removes and returns the root node in the heap.
| return | runtime |
|---|---|
| number | string | HeapNode | O(log(n)) |
console.log(minHeap.extractRoot()); // { key: 20, value: { name: 'test' } }
console.log(minHeap.extractRoot()); // { key: 30, value: 'something' }
console.log(minHeap.extractRoot()); // 40
console.log(maxHeap.extractRoot()); // { key: 'z', value: null }
console.log(maxHeap.extractRoot()); // 'x'
console.log(maxHeap.extractRoot()); // 'm'
| return | runtime |
|---|---|
| T | O(log(n)) |
console.log(customMaxHeap.extractRoot()); // { name: 'z' }
console.log(customMaxHeap.extractRoot()); // { name: 'x' }
console.log(customMaxHeap.extractRoot()); // { name: 'm' }
returns the root node without removing it.
| return | runtime |
|---|---|
| number | string | HeapNode | O(1) |
console.log(minHeap.root()); // 50
console.log(maxHeap.root()); // 'k'
| return | runtime |
|---|---|
| T | O(1) |
console.log(customMaxHeap.root()); // { name: 'k' }
returns a node with max key in MinHeap, or with min key in MaxHeap.
| return | runtime |
|---|---|
| number | string | HeapNode | O(1) |
console.log(minHeap.leaf()); // 90
console.log(maxHeap.leaf()); // 'b'
| return | runtime |
|---|---|
| T | O(1) |
console.log(customMaxHeap.leaf()); // { name: 'b' }
returns the number of nodes in the heap.
| return | runtime |
|---|---|
| number | O(1) |
console.log(minHeap.size()); // 4
console.log(maxHeap.size()); // 4
console.log(customMaxHeap.size()); // 4
creates a shallow copy of the heap.
| return | runtime |
|---|---|
| MinHeap | MaxHeap | CustomHeap | O(n) |
const minHeapClone = minHeap.clone();
minHeapClone.extractRoot();
console.log(minHeapClone.root()); // 60
console.log(minHeap.root()); // 50
const maxHeapClone = maxHeap.clone();
maxHeapClone.extractRoot();
console.log(maxHeapClone.root()); // { key: 'f', value: 'something' }
console.log(maxHeap.root()); // 'k'
const customMaxHeapClone = customMaxHeap.clone();
customMaxHeap.extractRoot();
console.log(customMaxHeap.root()); // { name: 'f' }
console.log(customMaxHeapClone.root()); // { name: 'k' }
checks if the heap is valid.
| return | runtime |
|---|---|
| boolean | O(log(n)) |
console.log(minHeap.isValid()); // true
console.log(maxHeap.isValid()); // true
console.log(customMaxHeap.isValid()); // true
fixes a heap by making the necessary changes in node positions.
| return | runtime |
|---|---|
| MinHeap | MaxHeap | CustomHeap | O(log(n)) |
console.log(minHeap.fix().isValid()); // true
console.log(maxHeap.fix().isValid()); // true
console.log(customMaxHeap.fix().isValid()); // true
implements Heap Sort and sorts a Max Heap in ascending order or a Min Heap in descending order.
| return | runtime |
|---|---|
| array<number|string|HeapNode> | O(n*log(n)) |
note: calling .sort() directly on a heap will mutate its nodes location. To avoid that, you might either sort a shallow copy. You can also use use .fix() to fix the mutated heap positions
console.log(maxHeap.clone().sort()); // sorting a copy of the heap
/*
[
'b',
{ key: 'c', value: { name: 'test' } },
{ key: 'f', value: 'something' },
'k'
]
*/
console.log(maxHeap.root()); // 'k'
console.log(minHeap.sort()); // will mutate the heap
/*
[ 90, 80, { key: 60, value: null }, 50 ]
*/
console.log(minHeap.isValid()); // false
minHeap.fix(); // fix it
console.log(minHeap.isValid()); // true
To sort a list of elements directtly using Heap Sort, it can be done like:
const ascSorted = MaxHeap.heapify([3, 7, 2, 10, 4, 9, 8, 5, 1, 6]).sort();
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
const descSorted = MinHeap.heapify([3, 7, 2, 10, 4, 9, 8, 5, 1, 6]).sort();
// [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
| return | runtime |
|---|---|
| array<T> | O(n*log(n)) |
// sorting custom max heap in ascending order
console.log(customMaxHeap.clone().sort());
/*
[
{ name: 'b' },
{ name: 'c' },
{ name: 'f' },
{ name: 'k' },
{ name: 'm' },
{ name: 'x' },
{ name: 'z' }
]
*/
clears the nodes in the heap.
| runtime |
|---|
| O(1) |
minHeap.clear();
maxHeap.clear();
console.log(minHeap.size()); // 0
console.log(minHeap.root()); // null
console.log(customMaxHeap.size()); // 0
console.log(customMaxHeap.root()); // null
Heapifies an existing list. It returns a heap instance as well as changing the list positions properly.
| params | return | runtime |
|---|---|---|
| list: array<number | string | HeapNode> | MinHeap | MaxHeap | O(n) |
const numList = [50, 80, 30, 90, 60, 40, 20];
MinHeap.heapify(numList);
console.log(numList); // [20, 60, 30, 90, 80, 50, 40]
const strList = ['m', 'x', 'f', 'b', 'z', 'k', 'c'];
const maxHeap = MaxHeap.heapify(strList);
console.log(strList); // ['z', 'x', 'k', 'b', 'm', 'f', 'c']
console.log(maxHeap.isValid()); // true
const objList = [
{ key: 50, value: 't1' },
{ key: 80, value: 't2' },
{ key: 30, value: 't3' },
{ key: 90, value: 't4' },
{ key: 60, value: 't5' },
{ key: 40, value: 't6' },
{ key: 20, value: 't7' }
];
MinHeap.heapify(objList);
console.log(objList);
/*
[
{ key: 20, value: 't7' },
{ key: 60, value: 't5' },
{ key: 30, value: 't3' },
{ key: 90, value: 't4' },
{ key: 80, value: 't2' },
{ key: 50, value: 't1' },
{ key: 40, value: 't6' }
]
*/
const numList = [50, 80, 30, 90, 60, 40, 20];
MinHeap.heapify<number>(numList);
console.log(numList); // [20, 60, 30, 90, 80, 50, 40]
const objList = [
{ key: 50, value: 't1' },
{ key: 80, value: 't2' },
{ key: 30, value: 't3' },
{ key: 90, value: 't4' },
{ key: 60, value: 't5' },
{ key: 40, value: 't6' },
{ key: 20, value: 't7' }
];
MinHeap.heapify<number, string>(objList);
console.log(objList);
/*
[
{ key: 20, value: 't7' },
{ key: 60, value: 't5' },
{ key: 30, value: 't3' },
{ key: 90, value: 't4' },
{ key: 80, value: 't2' },
{ key: 50, value: 't1' },
{ key: 40, value: 't6' }
]
*/
| params | return | runtime |
|---|---|---|
|
list: array<T>
comparator: (a: T, b: T) => number | CustomHeap<T> | O(n) |
const counts = [
{ count: 50 },
{ count: 80 },
{ count: 30 },
{ count: 90 },
{ count: 60 },
{ count: 40 },
{ count: 20 }
];
CustomHeap.heapify<{ count: number }>(counts, (a, b) => a.count - b.count);
console.log(counts); // minHeap list
/*
[
{ count: 20 },
{ count: 60 },
{ count: 30 },
{ count: 90 },
{ count: 80 },
{ count: 50 },
{ count: 40 }
]
*/
Checks if a given list is heapified.
| params | return | runtime |
|---|---|---|
| list: array<number | string | HeapNode> | boolean | O(log(n)) |
MinHeap.isHeapified([50, 80, 30, 90, 60, 40, 20]); // false
MinHeap.isHeapified([20, 60, 30, 90, 80, 50, 40]); // true
MaxHeap.isHeapified(['m', 'x', 'f', 'b', 'z', 'k', 'c']); // false
MaxHeap.isHeapified(['z', 'x', 'k', 'b', 'm', 'f', 'c']); // true
MinHeap.isHeapified<number>([20, 60, 30, 90, 80, 50, 40]); // true
MaxHeap.isHeapified<string>(['z', 'x', 'k', 'b', 'm', 'f', 'c']); // true
| params | return | runtime |
|---|---|---|
|
list: array<T>
comparator: (a: T, b: T) => number | boolean | O(log(n)) |
const counts = [
{ count: 20 },
{ count: 60 },
{ count: 30 },
{ count: 90 },
{ count: 80 },
{ count: 50 },
{ count: 40 }
];
console.log(CustomHeap.isHeapified<{ count: number }>(counts, (a, b) => a.count - b.count)); // true
grunt build
The MIT License. Full License is here
[3.2.0] - 2021-08-05
FAQs
Min/Max Heap & Heap Sort implementation in javascript
The npm package @datastructures-js/heap receives a total of 603,730 weekly downloads. As such, @datastructures-js/heap popularity was classified as popular.
We found that @datastructures-js/heap demonstrated a not healthy version release cadence and project activity because the last version was released 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.
Security News
Newly introduced telemetry in devenv 1.4 sparked a backlash over privacy concerns, leading to the removal of its AI-powered feature after strong community pushback.
Security News
TC39 met in Seattle and advanced 9 JavaScript proposals, including three to Stage 4, introducing new features and enhancements for a future ECMAScript release.
Security News
Deno 2.2 enhances Node.js compatibility, improves dependency management, adds OpenTelemetry support, and expands linting and task automation for developers.