A 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';The constructor accepts a callback to get the numeric priority from the queued element. If not passed, the constructor adds a default priority callback that returns the value of the element itself.
// empty queue with priority not being part of the queued element
const patientsQueue = new MinPriorityQueue(); // priority should be provided in .enqueue
// empty queue with priority returned from the queued element
const biddersQueue = new MaxPriorityQueue({ priority: (bid) => bid.value });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: any
priority: number |
MinPriorityQueue | MaxPriorityQueue | O(log(n)) |
// 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 |
|---|---|
| object | O(1) |
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 |
|---|---|
| object | O(1) |
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 |
|---|---|
| object | 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: { 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(patientsQueue.isEmpty()); // false
console.log(biddersQueue.isEmpty()); // falsereturns the number of elements in the queue.
| return | runtime |
|---|---|
| number | 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 | runtime |
|---|---|
| array<object> | 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: { 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) |
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
