@datastructures-js/priority-queue
Advanced tools
a performant priority queue implementation using a Heap data structure.
@datastructures-js/priority-queue is an npm package that provides a robust implementation of a priority queue data structure. It allows you to manage a collection of elements where each element is associated with a priority, and elements are served based on their priority.
Creating a Priority Queue
This code demonstrates how to create a new instance of a MinPriorityQueue using the @datastructures-js/priority-queue package.
const { MinPriorityQueue } = require('@datastructures-js/priority-queue');
const pq = new MinPriorityQueue();Adding Elements
This code shows how to add elements to the priority queue with associated priorities.
pq.enqueue('task1', 1);
pq.enqueue('task2', 2);Removing Elements
This code demonstrates how to remove and return the element with the highest priority from the priority queue.
const highestPriorityElement = pq.dequeue();Peeking at the Highest Priority Element
This code shows how to peek at the element with the highest priority without removing it from the queue.
const highestPriorityElement = pq.front();Checking if the Queue is Empty
This code demonstrates how to check if the priority queue is empty.
const isEmpty = pq.isEmpty();js-priority-queue is another npm package that provides a priority queue implementation. It supports both min and max priority queues and allows for custom comparison functions. Compared to @datastructures-js/priority-queue, js-priority-queue offers more flexibility in terms of custom comparison but may have a steeper learning curve.
heap is an npm package that provides a binary heap implementation, which can be used to create priority queues. It supports both min-heaps and max-heaps. Compared to @datastructures-js/priority-queue, heap is more low-level and may require more manual handling of heap properties.
priorityqueuejs is a simple and efficient priority queue implementation in JavaScript. It supports custom comparators and is easy to use. Compared to @datastructures-js/priority-queue, priorityqueuejs is more lightweight but may lack some advanced features.
A performant priority queue implementation using a Heap data structure.
npm install --save @datastructures-js/priority-queue
PriorityQueue in this repo is implemented as 3 types:
const {
PriorityQueue,
MinPriorityQueue,
MaxPriorityQueue
} = require('@datastructures-js/priority-queue');
import {
PriorityQueue,
MinPriorityQueue,
MaxPriorityQueue,
PriorityQueueOptions, // queue options interface
PriorityQueueItem // queue item interface for min/max queue
} from '@datastructures-js/priority-queue';
The constructor requires a compare callback to compare between queue elements. compare works similar to javascript sort callback: returning a number less or equal 0, means do not swap.
// empty queue with comparator
const employeesQueue = new PriorityQueue({
compare: (e1, e2) => {
if (e1.salary > e2.salary) return -1; // do not swap
if (e1.salary < e2.salary) return 1; // swap
// salaries are the same, compare rank
return e1.rank < e2.rank ? 1 : -1;
}
});
// queued element type
interface Employee {
name: string;
salary: number;
rank: number;
}
// empty queue with comparator
const employeesQueue = new PriorityQueue<Employee>({
compare: (e1: Employee, e2: Employee): number => {
if (e1.salary > e2.salary) return -1; // do not swap
if (e1.salary < e2.salary) return 1; // swap
// salaries are the same, compare rank
return e1.rank < e2.rank ? 1 : -1;
}
});
The constructor accepts a priority callback option to get the numeric priority from the queued element. If not passed, the constructor adds a default priority callback that returns the numeric value of the element itself. Use this queue type when the priority is a known value and does not require complex comparison.
// empty queue with priority is the element value itself.
const numbersQueue = new MinPriorityQueue();
// empty queue, will provide priority in .enqueue
const patientsQueue = new MinPriorityQueue();
// empty queue with priority returned from a prop of the queued object
const biddersQueue = new MaxPriorityQueue({ priority: (bid) => bid.value });
const numbersQueue = new MinPriorityQueue<number>();
const patientsQueue = new MinPriorityQueue<string>();
interface Bid {
name: string;
value: number;
}
const biddersQueue = new MaxPriorityQueue<Bid>({
priority: (bid: Bid) => bid.value
});
Creates a priority queue from an array of element-priority pairs.
MaxPriorityQueue.from([
['Alice', 19],
['Bob', 18],
['Charles', 20]
])
// { priority: 20, element: 'Charles' },
// { priority: 19, element: 'Alice' },
// { priority: 18, element: 'Bob' }
MinPriorityQueue.from([
['Alice', 19],
['Bob', 18],
['Charles', 20]
])
// { priority: 18, element: 'Bob' },
// { priority: 19, element: 'Alice' },
// { priority: 20, element: 'Charles' },
adds an element based on its comparison with other elements in the queue.
| params | return | runtime |
|---|---|---|
| element: T | PriorityQueue<T> | O(log(n)) |
employeesQueue
.enqueue({ name: 'employee 1', salary: 2000, rank: 1 })
.enqueue({ name: 'employee 2', salary: 1500, rank: 0 })
.enqueue({ name: 'employee 3', salary: 4000, rank: 4 })
.enqueue({ name: 'employee 4', salary: 2000, rank: 2 })
.enqueue({ name: 'employee 5', salary: 3000, rank: 3 });
adds an element with a numeric priority to the queue. Priority is not required here if a priority callback has been provided in the constructor. If passed here with a constructor callback, it will override the callback.
| params | return | runtime |
|---|---|---|
|
element: T
priority: number | MinPriorityQueue<T> | MaxPriorityQueue<T> | O(log(n)) |
// MinPriorityQueue Example, where priority is the number element itself
numbersQueue
.enqueue(10)
.enqueue(-7)
.enqueue(2)
.enqueue(-1)
.enqueue(-17)
.enqueue(33);
// MinPriorityQueue Example, where priority is the patient's turn
patientsQueue
.enqueue('patient y', 1) // highest priority
.enqueue('patient z', 3)
.enqueue('patient w', 4) // lowest priority
.enqueue('patient x', 2);
// MaxPriorityQueue Example, where priority is the bid's value.
biddersQueue
.enqueue({ name: 'bidder y', value: 1000 }) // lowest priority
.enqueue({ name: 'bidder w', value: 2500 })
.enqueue({ name: 'bidder z', value: 3500 }) // highest priority
.enqueue({ name: 'bidder x', value: 3000 });
returns the element with highest priority in the queue.
| return | runtime |
|---|---|
| T | O(1) |
console.log(employeesQueue.dequeue()); // { name: 'employee 3', salary: 4000, rank: 4 }
| return | runtime |
|---|---|
| PriorityQueueItem<T> | O(1) |
console.log(numbersQueue.front()); // { priority: -17, element: -17 }
console.log(patientsQueue.front()); // { priority: 1, element: 'patient y' }
console.log(biddersQueue.front()); // { priority: 3500, element: { name: 'bidder z', value: 3500 } }
returns an element with a lowest priority in the queue.
| return | runtime |
|---|---|
| T | O(1) |
console.log(employeesQueue.back()); // { name: 'employee 2', salary: 1500, rank: 0 }
| return | runtime |
|---|---|
| PriorityQueueItem<T> | O(1) |
console.log(numbersQueue.back()); // { priority: 33, element: 33 }
patientsQueue.enqueue('patient m', 4); // lowest priority
patientsQueue.enqueue('patient c', 4); // lowest priority
console.log(patientsQueue.back()); // { priority: 4, element: 'patient c' }
biddersQueue.enqueue({ name: 'bidder m', value: 1000 }); // lowest priority
biddersQueue.enqueue({ name: 'bidder c', value: 1000 }); // lowest priority
console.log(biddersQueue.back()); // { priority: 1000, element: { name: 'bidder y', value: 1000 } }
removes and returns the element with highest priority in the queue.
| return | runtime |
|---|---|
| T | O(log(n)) |
console.log(employeesQueue.dequeue()); // { name: 'employee 3', salary: 4000, rank: 4 }
console.log(employeesQueue.dequeue()); // { name: 'employee 5', salary: 3000, rank: 3 }
console.log(employeesQueue.dequeue()); // { name: 'employee 4', salary: 2000, rank: 2 }
console.log(employeesQueue.dequeue()); // { name: 'employee 1', salary: 2000, rank: 1 }
console.log(employeesQueue.dequeue()); // { name: 'employee 2', salary: 1500, rank: 0 }
| return | runtime |
|---|---|
| PriorityQueueItem<T> | O(log(n)) |
console.log(numbersQueue.dequeue()); // { priority: -17, element: -17 }
console.log(numbersQueue.front()); // { priority: -7, element: -7 }
console.log(patientsQueue.dequeue()); // { priority: 1, element: 'patient y' }
console.log(patientsQueue.front()); // { priority: 2, element: 'patient x' }
console.log(biddersQueue.dequeue()); // { priority: 3500, element: { name: 'bidder z', value: 3500 } }
console.log(biddersQueue.front()); // { priority: 3000, element: { name: 'bidder x', value: 3000 } }
checks if the queue is empty.
| return | runtime |
|---|---|
| boolean | O(1) |
console.log(numbersQueue.isEmpty()); // false
console.log(patientsQueue.isEmpty()); // false
console.log(biddersQueue.isEmpty()); // false
returns the number of elements in the queue.
| return | runtime |
|---|---|
| number | O(1) |
console.log(numbersQueue.size()); // 5
console.log(patientsQueue.size()); // 5
console.log(biddersQueue.size()); // 5
returns a sorted array of elements by their priorities from highest to lowest.
| return | runtime |
|---|---|
| T[] | O(n*log(n)) |
console.log(employeesQueue.toArray());
/*
[
{ name: 'employee 3', salary: 4000, rank: 4 },
{ name: 'employee 5', salary: 3000, rank: 3 },
{ name: 'employee 4', salary: 2000, rank: 2 },
{ name: 'employee 1', salary: 2000, rank: 1 },
{ name: 'employee 2', salary: 1500, rank: 0 }
]
*/
| return | runtime |
|---|---|
| PriorityQueueItem<T>[] | O(n*log(n)) |
console.log(numbersQueue.toArray());
/*
[
{ priority: -7, element: -7 },
{ priority: -1, element: -1 },
{ priority: 2, element: 2 },
{ priority: 10, element: 10 },
{ priority: 33, element: 33 }
]
*/
console.log(patientsQueue.toArray());
/*
[
{ priority: 2, element: 'patient x' },
{ priority: 3, element: 'patient z' },
{ priority: 4, element: 'patient c' },
{ priority: 4, element: 'patient w' },
{ priority: 4, element: 'patient m' }
]
*/
console.log(biddersQueue.toArray());
/*
[
{ priority: 3000, element: { name: 'bidder x', value: 3000 } },
{ priority: 2500, element: { name: 'bidder w', value: 2500 } },
{ priority: 1000, element: { name: 'bidder y', value: 1000 } },
{ priority: 1000, element: { name: 'bidder m', value: 1000 } },
{ priority: 1000, element: { name: 'bidder c', value: 1000 } }
]
*/
clears all elements in the queue.
| runtime |
|---|
| O(1) |
numbersQueue.clear();
console.log(numbersQueue.size()); // 0
console.log(numbersQueue.front()); // null
console.log(numbersQueue.dequeue()); // null
patientsQueue.clear();
console.log(patientsQueue.size()); // 0
console.log(patientsQueue.front()); // null
console.log(patientsQueue.dequeue()); // null
biddersQueue.clear();
console.log(biddersQueue.size()); // 0
console.log(biddersQueue.front()); // null
console.log(biddersQueue.dequeue()); // null
grunt build
The MIT License. Full License is here
FAQs
A heap-based implementation of priority queue in javascript with typescript support.
The npm package @datastructures-js/priority-queue receives a total of 522,862 weekly downloads. As such, @datastructures-js/priority-queue popularity was classified as popular.
We found that @datastructures-js/priority-queue 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
Deno 2.2 enhances Node.js compatibility, improves dependency management, adds OpenTelemetry support, and expands linting and task automation for developers.
Security News
React's CRA deprecation announcement sparked community criticism over framework recommendations, leading to quick updates acknowledging build tools like Vite as valid alternatives.
Security News
Ransomware payment rates hit an all-time low in 2024 as law enforcement crackdowns, stronger defenses, and shifting policies make attacks riskier and less profitable.