Package Exports

@datastructures-js/priority-queue

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (@datastructures-js/priority-queue) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

@datastructures-js/priority-queue

A performant priority queue implementation using a Heap data structure.

Install
require
import
API
Build
License

Install

npm install --save @datastructures-js/priority-queue

API

PriorityQueue in this repo is implemented as two types: 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,
  PriorityQueueOptions, // queue options interface
  PriorityQueueItem // queue item interface
} from '@datastructures-js/priority-queue';

constructor

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 numeric value of the element itself.

JS

// empty queue with default priority 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 });

TS

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
});

.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: 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 });

.front()

returns the element with highest priority in the queue.

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 } }

.back()

returns an element with a lowest priority in the queue.

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 } }

.dequeue()

removes and returns the element with highest priority in the queue.

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 } }

.isEmpty()

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

.size()

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

.toArray()

returns a sorted array of elements by their priorities from highest to lowest.

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 } }
]
*/

.clear()

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

Build

grunt build

License

The MIT License. Full License is here