@datastructures-js/priority-queue

A heap-based implementation of priority queue in javascript with typescript support.

Contents

• Install
• require
• import
• API
  • constructor
  • fromArray
  • enqueue (push)
  • front
  • back
  • dequeue (pop)
  • contains
  • remove
  • isEmpty
  • size
  • toArray
  • Symbol.iterator
  • clear
• Build
• License

Install

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

API

PriorityQueue class allows using a compare function between values. MinPriorityQueue & MaxPriorityQueue can be used for primitive values and objects with known comparison prop.

require

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

import

1import {
2  PriorityQueue,
3  MinPriorityQueue,
4  MaxPriorityQueue,
5  ICompare,
6  IGetCompareValue,
7} from '@datastructures-js/priority-queue';

constructor

PriorityQueue

constructor requires a compare function that works similar to javascript sort callback, returning a number bigger than 0, means swap elements.

TS

1interface ICar {
2  year: number;
3  price: number;
4}
5
6const compareCars: ICompare<ICar> = (a: ICar, b: ICar) => {
7  if (a.year > b.year) {
8    return -1;
9  }
10  if (a.year < b.year) {
11    // prioritize newest cars
12    return 1;
13  }
14  // with lowest price
15  return a.price < b.price ? -1 : 1;
16};
17
18const carsQueue = new PriorityQueue<ICar>(compareCars);

JS

1const carsQueue = new PriorityQueue((a, b) => {
2    if (a.year > b.year) {
3      return -1;
4    }
5    if (a.year < b.year) {
6      // prioratize newest cars
7      return 1;
8    }
9    // with lowest price
10    return a.price < b.price ? -1 : 1;
11  }
12);

MinPriorityQueue, MaxPriorityQueue

constructor requires a callback for object values to indicate which prop is used for comparison, and does not require any for primitive values like numbers or strings.

TS

1const numbersQueue = new MinPriorityQueue<number>();
2
3interface IBid {
4  id: number;
5  value: number;
6}
7const getBidValue: IGetCompareValue<IBid> = (bid) => bid.value;
8const bidsQueue = new MaxPriorityQueue<IBid>(getBidValue);

JS

1const numbersQueue = new MinPriorityQueue();
2const bidsQueue = new MaxPriorityQueue((bid) => bid.value);

Legacy Compare Function (v5 compatibility)

For backward compatibility with v5, you can also pass a compare function in an options object:

1// MinPriorityQueue with legacy compare
2const minQueue = new MinPriorityQueue({ compare: (a, b) => a - b });
3
4// MaxPriorityQueue with legacy compare
5const maxQueue = new MaxPriorityQueue({ compare: (a, b) => a - b });

This format is supported for backward compatibility with v5 of the library.

fromArray

If the queue is being created from an existing array, and there is no desire to use an extra O(n) space, this static function can turn an array into a priority queue in O(n) runtime.

PriorityQueue

TS

1const numbers = [3, -2, 5, 0, -1, -5, 4];
2
3const pq = PriorityQueue.fromArray<number>(numbers, (a, b) => a - b);
4
5console.log(numbers); // [-5, -1, -2, 3, 0, 5, 4]
6pq.dequeue(); // -5
7pq.dequeue(); // -2
8pq.dequeue(); // -1
9console.log(numbers); // [ 0, 3, 4, 5 ]

JS

1const numbers = [3, -2, 5, 0, -1, -5, 4];
2
3const pq = PriorityQueue.fromArray(numbers, (a, b) => a - b);
4
5console.log(numbers); // [-5, -1, -2, 3, 0, 5, 4]
6pq.dequeue(); // -5
7pq.dequeue(); // -2
8pq.dequeue(); // -1
9console.log(numbers); // [ 0, 3, 4, 5 ]

MinPriorityQueue, MaxPriorityQueue

TS

1const numbers = [3, -2, 5, 0, -1, -5, 4];
2
3const mpq = MaxPriorityQueue.fromArray<number>(numbers);
4
5console.log(numbers); // [-5, -1, -2, 3, 0, 5, 4]
6mpq.dequeue(); // 5
7mpq.dequeue(); // 4
8mpq.dequeue(); // 3
9console.log(numbers); // [ 0, -1, -5, -2 ]

JS

1const numbers = [3, -2, 5, 0, -1, -5, 4];
2
3const mpq = MaxPriorityQueue.fromArray(numbers);
4
5console.log(numbers); // [-5, -1, -2, 3, 0, 5, 4]
6mpq.dequeue(); // 5
7mpq.dequeue(); // 4
8mpq.dequeue(); // 3
9console.log(numbers); // [ 0, -1, -5, -2 ]

enqueue (push)

adds a value based on its comparison with other values in the queue in O(log(n)) runtime.

1const cars = [
2  { year: 2013, price: 35000 },
3  { year: 2010, price: 2000 },
4  { year: 2013, price: 30000 },
5  { year: 2017, price: 50000 },
6  { year: 2013, price: 25000 },
7  { year: 2015, price: 40000 },
8  { year: 2022, price: 70000 }
9];
10cars.forEach((car) => carsQueue.enqueue(car));
11
12const numbers = [3, -2, 5, 0, -1, -5, 4];
13numbers.forEach((num) => numbersQueue.push(num)); // push is an alias for enqueue
14
15const bids = [
16  { id: 1, value: 1000 },
17  { id: 2, value: 20000 },
18  { id: 3, value: 1000 },
19  { id: 4, value: 1500 },
20  { id: 5, value: 12000 },
21  { id: 6, value: 4000 },
22  { id: 7, value: 8000 }
23];
24bids.forEach((bid) => bidsQueue.enqueue(bid));

front

peeks on the value with highest priority in the queue.

1console.log(carsQueue.front()); // { year: 2022, price: 70000 }
2console.log(numbersQueue.front()); // -5
3console.log(bidsQueue.front()); // { id: 2, value: 20000 }

back

peeks on the value with a lowest priority in the queue.

1console.log(carsQueue.back()); // { year: 2010, price: 2000 }
2console.log(numbersQueue.back()); // 5
3console.log(bidsQueue.back()); // { id: 1, value: 1000 }

dequeue (pop)

removes and returns the element with highest priority in the queue in O(log(n)) runtime.

1console.log(carsQueue.dequeue()); // { year: 2022, price: 70000 }
2console.log(carsQueue.dequeue()); // { year: 2017, price: 50000 }
3console.log(carsQueue.dequeue()); // { year: 2015, price: 40000 }
4
5console.log(numbersQueue.dequeue()); // -5
6console.log(numbersQueue.dequeue()); // -2
7console.log(numbersQueue.dequeue()); // -1
8
9console.log(bidsQueue.pop()); // { id: 2, value: 20000 }
10console.log(bidsQueue.pop()); // { id: 5, value: 12000 }
11console.log(bidsQueue.pop()); // { id: 7, value: 8000 }

contains

checks if the queue contains an element that meet a criteria in O(n*log(n)) runtime.

1carsQueue.contains((car) => car.price === 50000); // true
2carsQueue.contains((car) => car.price === 200000); // false
3numbersQueue.contains((n) => n === 4); // true
4numbersQueue.contains((n) => n === 10); // false

remove

removes all elements that meet a criteria in O(n*log(n)) runtime and returns a list of the removed elements.

1carsQueue.remove((car) => car.price === 35000); // [{ year: 2013, price: 35000 }]
2
3numbersQueue.remove((n) => n === 4); // [4]
4
5bidsQueue.remove((bid) => bid.id === 3); // [{ id: 3, value: 1000 }]

isEmpty

checks if the queue is empty.

1console.log(carsQueue.isEmpty()); // false
2console.log(numbersQueue.isEmpty()); // false
3console.log(bidsQueue.isEmpty()); // false

size

returns the number of elements in the queue.

1console.log(carsQueue.size()); // 3
2console.log(numbersQueue.size()); // 3
3console.log(bidsQueue.size()); // 3

toArray

returns a sorted array of elements by their priorities from highest to lowest in O(n*log(n)) runtime.

1console.log(carsQueue.toArray());
2/*
3[
4  { year: 2013, price: 25000 },
5  { year: 2013, price: 30000 },
6  { year: 2010, price: 2000 }
7]
8*/
9
10console.log(numbersQueue.toArray()); // [ 0, 3, 5 ]
11
12console.log(bidsQueue.toArray());
13/*
14[
15  { id: 6, value: 4000 },
16  { id: 4, value: 1500 },
17  { id: 1, value: 1000 }
18]
19*/

Symbol.iterator

The queues implement a Symbol.iterator that makes them iterable on pop.

1console.log([...carsQueue]);
2/*
3[
4  { year: 2013, price: 25000 },
5  { year: 2013, price: 30000 },
6  { year: 2010, price: 2000 }
7]
8*/
9console.log(carsQueue.size()); // 0
10
11console.log([...numbersQueue]); // [ 0, 3, 5 ]
12console.log(numbersQueue.size()); // 0
13
14for (const bid of bidsQueue) {
15  console.log(bid);
16}
17/*
18{ id: 6, value: 4000 },
19{ id: 4, value: 1500 },
20{ id: 1, value: 1000 }
21*/
22console.log(bidsHeap.size()); // 0

clear

clears all elements in the queue.

1carsQueue.clear();
2console.log(carsQueue.size()); // 0
3console.log(carsQueue.front()); // null
4console.log(carsQueue.dequeue()); // null
5console.log(carsQueue.isEmpty()); // true
6
7numbersQueue.clear();
8console.log(numbersQueue.size()); // 0
9console.log(numbersQueue.front()); // null
10console.log(numbersQueue.dequeue()); // null
11console.log(numbersQueue.isEmpty()); // true
12
13bidsQueue.clear();
14console.log(bidsQueue.size()); // 0
15console.log(bidsQueue.front()); // null
16console.log(bidsQueue.dequeue()); // null
17console.log(bidsQueue.isEmpty()); // true

Build

grunt build

License

The MIT License. Full License is here