Security News
Research
Data Theft Repackaged: A Case Study in Malicious Wrapper Packages on npm
The Socket Research Team breaks down a malicious wrapper package that uses obfuscation to harvest credentials and exfiltrate sensitive data.
Efficient Binary heap (priority queue, binary tree) data structure for JavaScript / TypeScript. Includes JavaScript methods, Python's heapq module methods, and Java's PriorityQueue methods.
heap-js is a JavaScript implementation of a binary heap data structure. It provides efficient methods for priority queue operations, such as inserting elements, finding the minimum or maximum element, and removing elements. This package is useful for algorithms that require priority queues, such as Dijkstra's algorithm for shortest paths, Huffman coding, and more.
MinHeap
This feature allows you to create a MinHeap, where the smallest element is always at the root. The code sample demonstrates how to insert elements into the MinHeap, peek at the smallest element, and remove elements in ascending order.
const { MinHeap } = require('heap-js');
const minHeap = new MinHeap();
minHeap.push(3);
minHeap.push(1);
minHeap.push(2);
console.log(minHeap.peek()); // Output: 1
console.log(minHeap.pop()); // Output: 1
console.log(minHeap.pop()); // Output: 2
MaxHeap
This feature allows you to create a MaxHeap, where the largest element is always at the root. The code sample demonstrates how to insert elements into the MaxHeap, peek at the largest element, and remove elements in descending order.
const { MaxHeap } = require('heap-js');
const maxHeap = new MaxHeap();
maxHeap.push(3);
maxHeap.push(1);
maxHeap.push(2);
console.log(maxHeap.peek()); // Output: 3
console.log(maxHeap.pop()); // Output: 3
console.log(maxHeap.pop()); // Output: 2
Custom Comparator
This feature allows you to create a heap with a custom comparator function. The code sample demonstrates how to create a MinHeap for objects with a 'priority' property, and how to insert and remove elements based on their priority.
const { MinHeap } = require('heap-js');
const customHeap = new MinHeap({
compare: (a, b) => a.priority - b.priority
});
customHeap.push({ value: 'task1', priority: 2 });
customHeap.push({ value: 'task2', priority: 1 });
console.log(customHeap.pop().value); // Output: 'task2'
The 'heap' package provides a binary heap implementation with similar functionalities to heap-js. It supports both MinHeap and MaxHeap operations and allows custom comparator functions. However, heap-js is often preferred for its more modern API and better performance in certain use cases.
The 'js-priority-queue' package offers a priority queue implementation using a binary heap. It supports custom comparator functions and provides methods for inserting and removing elements. Compared to heap-js, js-priority-queue is more focused on priority queue operations and may have a simpler API for those specific needs.
The 'priorityqueuejs' package provides a priority queue implementation with a binary heap. It supports custom comparator functions and offers methods for inserting and removing elements. While similar to heap-js, priorityqueuejs is designed to be lightweight and easy to use, making it a good choice for simpler applications.
Efficient Binary heap (priority queue, binary tree) data structure for JavaScript / TypeScript.
Now with support for async comparators with the new HeapAsync
class!
Includes JavaScript methods, Python's heapq module methods, and Java's PriorityQueue methods.
Easy to use, known interfaces, tested, and well-documented JavaScript binary heap library.
Instances are integer min heap
by default.
It depends on your usage, but for some scenarios, it is much faster:
heap vs array: push + pop/unshift 50
heap x 72,130 ops/sec ±0.50% (93 runs sampled)
array x 121 ops/sec ±78.09% (5 runs sampled)
heap vs array: push + peek 20
heap x 622,332 ops/sec ±27.93% (63 runs sampled)
array x 207 ops/sec ±78.18% (5 runs sampled)
heap vs array: push + top(1) of 100
heap x 124,835 ops/sec ±40.37% (61 runs sampled)
array x 123 ops/sec ±78.49% (5 runs sampled)
heap vs array: push + top(50) of 100
heap x 59,210 ops/sec ±17.66% (82 runs sampled)
array x 125 ops/sec ±78.79% (5 runs sampled)
limit
property to support negative, Infinity, and NaN values. They will be set as 0
and the heap will not be limited.setLimit
method to set the limit of the heap. It returns NaN
if the limit is negative, or NaN. This method is useful to check if the limit was set as expected.indexOf
method to find the first index of an element in the heap.indexOfEvery
method to find all indexes of an element in the heap.remove
method to use the indexOf
method.contains
method to use the indexOf
method.HeapAsync
class, with async methods and supporting async comparators. It is a drop-in replacement for the Heap
class with Promises..iterator()
method to follow Java's PriorityQueue implementation:
The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order.
Notice that using the heap directly as an iterator will consume the heap, as Python's heapq
implementation does.
Heap.nlargest
as in heapq
.Heap.nsmallest
as in heapq
.top
/ bottom
input to force an integer.The main breaking change is that now top(N)
does NOT sort the output, because sorting should not be part of the spec for a priority queue. The output is the top N elements, and they will be partially ordered with the peek at index 0
by definition.
top(N)
is unordered, only the first element is guaranteed to be the top priority element.top(N)
algorithms.Iterator
interface and iterator()
method.A heap where the smallest element is always at the top. It is the default heap.
import { Heap } from 'heap-js';
// Min Heap by default
const minHeap = new Heap();
// Initialize the heap with an array
minHeap.init([5, 18, 1]);
// Push a new value
minHeap.push(2);
console.log(minHeap.peek()); //> 1
console.log(minHeap.pop()); //> 1
console.log(minHeap.peek()); //> 2
A heap where the largest element is always at the top.
import { Heap } from 'heap-js';
// Max Heap
const maxHeap = new Heap(Heap.maxComparator);
// Initialize the heap with an array
maxHeap.init([3, 4, 1, 12, 8]);
// Push a new value
maxHeap.push(2);
console.log(maxHeap.peek()); //> 12
console.log(maxHeap.pop()); //> 12
console.log(maxHeap.peek()); //> 8
A heap where the most important element is always at the top, but the elements are objects with a priority
property.
import { Heap } from 'heap-js';
const customPriorityComparator = (a, b) => a.priority - b.priority;
// Custom Heap
const customHeap = new Heap(customPriorityComparator);
// Initialize the heap with an array
customHeap.init([{ priority: 5 }, { priority: 18 }, { priority: 1 }]);
// Push a new value
customHeap.push({ priority: 2 });
console.log(customHeap.peek()); //> { priority: 1 }
console.log(customHeap.pop()); //> { priority: 1 }
console.log(customHeap.peek()); //> { priority: 2 }
A heap where the most important element is always at the top, the elements are objects with a priority
property, and the comparator function is asynchronous. Implements the same interface as Heap
, but almost all methods return a Promise
.
import { HeapAsync } from 'heap-js';
const customPriorityComparator = (a, b) => Promise.resolve(a.priority - b.priority);
// Custom HeapAsync
const customHeap = new HeapAsync(customPriorityComparator);
// Initialize the heap with an array
await customHeap.init([{ priority: 5 }, { priority: 18 }, { priority: 1 }]);
// Push a new value
await customHeap.push({ priority: 2 });
console.log(customHeap.peek()); //> { priority: 1 }
console.log(await customHeap.pop()); //> { priority: 1 }
console.log(await customHeap.peek()); //> { priority: 2 }
Iterates over the heap consuming it, and guarantees to traverse the elements of the heap in the order of priority. Useful.
const { Heap } = require('heap-js');
// Get all tasks from the database
const tasks = db.collection.find().toArray();
// The most important task has the lowest priority value
const customPriorityComparator = (a, b) => a.priority - b.priority;
// Create the priority queue
const priorityQueue = new Heap(customPriorityComparator);
// Initialize the priority queue with the tasks
priorityQueue.init(tasks);
// Iterator that will consume the heap while traversing it in the order of priority
for (const task of priorityQueue) {
console.log(task);
}
Iterates over the heap without consuming it, but does not guarantee to traverse the elements of the heap in any particular order. Barely useful.
const { Heap } = require('heap-js');
// Get all tasks from the database
const tasks = db.collection.find().toArray();
// The most important task has the lowest priority value
const customPriorityComparator = (a, b) => a.priority - b.priority;
const priorityQueue = new Heap(customPriorityComparator);
// Initialize the priority queue with the tasks
priorityQueue.init(tasks);
// Iterator, the Java way, that will not consume the heap BUT does not guarantee to traverse the elements of the heap in any particular order. Barely useful.
for (const task of priorityQueue.iterator()) {
console.log(task);
}
import { Heap } from 'heap-js';
const numbers = [2, 3, 7, 5];
// Changes the array elements order into a heap in-place
Heap.heapify(numbers);
console.log(numbers); //> [ 2, 3, 5, 7 ]
// Pushes a new value to the heap
Heap.heappush(numbers, 1);
console.log(numbers); //> [ 1, 2, 5, 7, 3 ]
yarn add heap-js # if you use yarn
npm install --save heap-js # if you use npm
new Heap([comparator]);
new HeapAsync([asyncComparator]);
Heap.minComparator
: Uses less-than operator to compare elements. It is the default comparator.Heap.maxComparator
: Uses greater-than operator to compare elements.Heap.minComparatorNumber
: Uses subtraction a - b
to compare elements.Heap.maxComparatorNumber
: Uses subtraction b - a
to compare elements.for (const value of heap)
directly usable as an Iterator, consumes the heap.length
of the heap.limit
the number of elements in the heap.pop()
the top element.push(...elements)
one or more elements to the heap.pushpop(element)
faster than push
& pop
.replace(element)
faster than pop
& push
.top(number?)
most valuable elements from the heap.bottom(number?)
least valuable elements from the heap.indexOf(element, fn?)
returns the internal index of the first occurrence of the element in the heap.indexOfEvery(element, fn?)
returns an array with the internal indexes of all occurrences of the element in the heap.PriorityQueue
interfaceadd(element)
to the heap.addAll([element, element, ... ])
to the heap, faster than loop add
.clear()
clone()
comparator()
contains(element, fn?)
element()
alias of peek()
isEmpty()
iterator()
returns the same as toArray()
because it is iterable and follows Java's implementation. Barely useful. Use for (const value of heap)
instead.offer(element)
alias of add(element)
peek()
poll()
alias of pop()
remove(element?)
removeAll()
alias of clear()
size()
alias of length
toArray()
toString()
To do:
containsAll
equals
retainAll
heapq
interfaceHeap.heapify(array, comparator?)
that converts an array to an array-heap.Heap.heappop(heapArray, comparator?)
that takes the peek of the array-heap.Heap.heappush(heapArray, item, comparator?)
that appends elements to the array-heap.Heap.heappushpop(heapArray, item, comparator?)
faster than heappush
& heappop
.Heap.heapreplace(heapArray, item, comparator?)
faster than heappop
& heappush
.Heap.nlargest(n, iterable, comparator?)
that gets the n
most valuable elements of an iterable.Heap.nsmallest(n, iterable, comparator?)
that gets the n
least valuable elements of an iterable.Extras:
Heap.heaptop(n, heapArray, comparator?)
that returns the n
most valuable elements of the array-heapHeap.heapbottom(n, heapArray, comparator?)
that returns the n
least valuable elements of the array-heapTo do:
merge(...iterables, comparator?)
https://ignlg.github.io/heap-js/
Development of Heap.js happens in the open on GitHub, and I am grateful to the community for contributing bug fixes and improvements.
yarn
npm run test
npm run benchmarks
Heap.js is BSD licensed.
FAQs
Efficient Binary heap (priority queue, binary tree) data structure for JavaScript / TypeScript. Includes JavaScript methods, Python's heapq module methods, and Java's PriorityQueue methods.
The npm package heap-js receives a total of 1,139,790 weekly downloads. As such, heap-js popularity was classified as popular.
We found that heap-js 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.
Security News
Research
The Socket Research Team breaks down a malicious wrapper package that uses obfuscation to harvest credentials and exfiltrate sensitive data.
Research
Security News
Attackers used a malicious npm package typosquatting a popular ESLint plugin to steal sensitive data, execute commands, and exploit developer systems.
Security News
The Ultralytics' PyPI Package was compromised four times in one weekend through GitHub Actions cache poisoning and failure to rotate previously compromised API tokens.