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
- constructor
- .enqueue
- .front
- .back
- .dequeue
- .isEmpty
- .size
- .toArray
- .clear
Build
License

Install

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

API

PriorityQueue in this repo is implemented as 3 types:

PriorityQueue that accepts a custom comparator between elements.
MinPriorityQueue which considers an element with smaller priority number as higher in priority.
MaxPriorityQueue which cosiders an element with bigger priority number as higher in priority.

require

const {
  PriorityQueue,
  MinPriorityQueue,
  MaxPriorityQueue
} = require('@datastructures-js/priority-queue');

import

import {
  PriorityQueue,
  MinPriorityQueue,
  MaxPriorityQueue,
  PriorityQueueOptions, // queue options interface
  PriorityQueueItem // queue item interface for min/max queue
} from '@datastructures-js/priority-queue';

constructor

PriorityQueue

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.

JS

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

TS

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

MinPriorityQueue/MaxPriorityQueue

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.

JS

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

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

PriorityQueue - .enqueue(element)

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

MinPriorityQueue/MaxPriorityQueue - .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.

PriorityQueue

return	runtime
T	O(1)

console.log(employeesQueue.dequeue()); // { name: 'employee 3', salary: 4000, rank: 4 }

MinPriorityQueue/MaxPriorityQueue

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.

PriorityQueue

return	runtime
T	O(1)

console.log(employeesQueue.back()); // { name: 'employee 2', salary: 1500, rank: 0 }

MinPriorityQueue/MaxPriorityQueue

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.

PriorityQueue

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 }

MinPriorityQueue/MaxPriorityQueue

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.

PriorityQueue

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

MinPriorityQueue/MaxPriorityQueue

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