A highly performant priority queue implementation using a Heap data structure.
npm install --save @datastructures-js/priority-queueThere are two types of PriorityQueue in this repo: MinPriorityQueue which uses a MinHeap and considers an element with smaller priority number as higher in priority. And MaxPriorityQueue which uses a MaxHeap and cosiders an element with bigger priority number as higher in priority.
const { MinPriorityQueue, MaxPriorityQueue } = require('@datastructures-js/priority-queue');import { MinPriorityQueue, MaxPriorityQueue } from '@datastructures-js/priority-queue';const patientsQueue = new MinPriorityQueue();
const biddersQueue = new MaxPriorityQueue();adds an element with a priority (number) to the queue.
| params | ||
|---|---|---|
| name | type | |
| element | object | |
| priority | number | |
| runtime |
|---|
| O(log(n)) |
// MinPriorityQueue Example, where priority is the turn for example
patientsQueue.enqueue('patient y', 1); // highest priority
patientsQueue.enqueue('patient z', 3);
patientsQueue.enqueue('patient w', 4); // lowest priority
patientsQueue.enqueue('patient x', 2);
// MaxPriorityQueue Example, where priority is the bid for example
biddersQueue.enqueue('bidder y', 1000); // lowest priority
biddersQueue.enqueue('bidder w', 2500);
biddersQueue.enqueue('bidder z', 3500); // highest priority
biddersQueue.enqueue('bidder x', 3000);returns the element with highest priority in the queue.
| return | description |
|---|---|
| object | object literal with "priority" and "element" props |
| runtime |
|---|
| O(1) |
console.log(patientsQueue.front()); // { priority: 1, element: 'patient y' }
console.log(biddersQueue.front()); // { priority: 3500, element: 'bidder z' }returns an element with lowest priority in the queue. If multiple elements exist at the lowest priority, the one that was inserted first will be returned.
| return | description |
|---|---|
| object | object literal with "priority" and "element" props |
| runtime |
|---|
| O(1) |
patientsQueue.enqueue('patient m', 4); // lowest priority
patientsQueue.enqueue('patient c', 4); // lowest priority
console.log(patientsQueue.back()); // { priority: 4, element: 'patient w' }
biddersQueue.enqueue('bidder m', 1000); // lowest priority
biddersQueue.enqueue('bidder c', 1000); // lowest priority
console.log(biddersQueue.back()); // { priority: 1000, element: 'bidder y' }removes and returns the element with highest priority in the queue.
| return | description |
|---|---|
| object | object literal with "priority" and "element" props |
| runtime |
|---|
| O(log(n)) |
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: 'bidder z' }
console.log(biddersQueue.front()); // { priority: 3000, element: 'bidder x' }checks if the queue is empty.
| return |
|---|
| boolean |
| runtime |
|---|
| O(1) |
console.log(patientsQueue.isEmpty()); // false
console.log(biddersQueue.isEmpty()); // falsereturns the number of elements in the queue.
| return |
|---|
| number |
| runtime |
|---|
| O(1) |
console.log(patientsQueue.size()); // 5
console.log(biddersQueue.size()); // 5returns a sorted array of elements by their priorities from highest to lowest.
| return | description |
|---|---|
| array | an array of object literals with "priority" & "element" props |
| runtime |
|---|
| O(n*log(n)) |
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: 'bidder x' },
{ priority: 2500, element: 'bidder w' },
{ priority: 1000, element: 'bidder y' },
{ priority: 1000, element: 'bidder m' },
{ priority: 1000, element: 'bidder c' }
]
*/clears all elements in the queue.
| runtime |
|---|
| O(1) |
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()); // nullgrunt build
The MIT License. Full License is here