@datastructures-js/priority-queue
A performant priority queue implementation using a Heap data structure.
Table of Contents
Install
npm install --save @datastructures-js/priority-queue
API
There 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.
require
const { MinPriorityQueue, MaxPriorityQueue } = require('@datastructures-js/priority-queue');
import
import { MinPriorityQueue, MaxPriorityQueue } from '@datastructures-js/priority-queue';
Construction
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.
const patientsQueue = new MinPriorityQueue();
const biddersQueue = new MaxPriorityQueue({ priority: (bid) => bid.value });
.enqueue(element[, priority])
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)) |
patientsQueue
.enqueue('patient y', 1);
.enqueue('patient z', 3);
.enqueue('patient w', 4);
.enqueue('patient x', 2);
biddersQueue
.enqueue({ name: 'bidder y', value: 1000 });
.enqueue({ name: 'bidder w', value: 2500 });
.enqueue({ name: 'bidder z', value: 3500 });
.enqueue({ name: 'bidder x', value: 3000 });
.front()
returns the element with highest priority in the queue.
console.log(patientsQueue.front());
console.log(biddersQueue.front());
.back()
returns an element with a lowest priority in the queue.
patientsQueue.enqueue('patient m', 4);
patientsQueue.enqueue('patient c', 4);
console.log(patientsQueue.back());
biddersQueue.enqueue({ name: 'bidder m', value: 1000 });
biddersQueue.enqueue({ name: 'bidder c', value: 1000 });
console.log(biddersQueue.back());
.dequeue()
removes and returns the element with highest priority in the queue.
return | runtime |
---|
object | O(log(n)) |
console.log(patientsQueue.dequeue());
console.log(patientsQueue.front());
console.log(biddersQueue.dequeue());
console.log(biddersQueue.front());
.isEmpty()
checks if the queue is empty.
console.log(patientsQueue.isEmpty());
console.log(biddersQueue.isEmpty());
.size()
returns the number of elements in the queue.
console.log(patientsQueue.size());
console.log(biddersQueue.size());
.toArray()
returns a sorted array of elements by their priorities from highest to lowest.
return | runtime |
---|
array<object> | O(n*log(n)) |
console.log(patientsQueue.toArray());
console.log(biddersQueue.toArray());
.clear()
clears all elements in the queue.
patientsQueue.clear();
console.log(patientsQueue.size());
console.log(patientsQueue.front());
console.log(patientsQueue.dequeue());
biddersQueue.clear();
console.log(biddersQueue.size());
console.log(biddersQueue.front());
console.log(biddersQueue.dequeue());
Build
grunt build
License
The MIT License. Full License is here