@datastructures-js/priority-queue

What is @datastructures-js/priority-queue?

@datastructures-js/priority-queue is an npm package that provides a robust implementation of a priority queue data structure. It allows you to manage a collection of elements where each element is associated with a priority, and elements are served based on their priority.

What are @datastructures-js/priority-queue's main functionalities?

Creating a Priority Queue

This code demonstrates how to create a new instance of a MinPriorityQueue using the @datastructures-js/priority-queue package.

const { MinPriorityQueue } = require('@datastructures-js/priority-queue');
const pq = new MinPriorityQueue();

Adding Elements

This code shows how to add elements to the priority queue with associated priorities.

pq.enqueue('task1', 1);
pq.enqueue('task2', 2);

Removing Elements

This code demonstrates how to remove and return the element with the highest priority from the priority queue.

const highestPriorityElement = pq.dequeue();

Peeking at the Highest Priority Element

This code shows how to peek at the element with the highest priority without removing it from the queue.

const highestPriorityElement = pq.front();

Checking if the Queue is Empty

This code demonstrates how to check if the priority queue is empty.

const isEmpty = pq.isEmpty();

Other packages similar to @datastructures-js/priority-queue

js-priority-queue

js-priority-queue is another npm package that provides a priority queue implementation. It supports both min and max priority queues and allows for custom comparison functions. Compared to @datastructures-js/priority-queue, js-priority-queue offers more flexibility in terms of custom comparison but may have a steeper learning curve.

heap

heap is an npm package that provides a binary heap implementation, which can be used to create priority queues. It supports both min-heaps and max-heaps. Compared to @datastructures-js/priority-queue, heap is more low-level and may require more manual handling of heap properties.

priorityqueuejs

priorityqueuejs is a simple and efficient priority queue implementation in JavaScript. It supports custom comparators and is easy to use. Compared to @datastructures-js/priority-queue, priorityqueuejs is more lightweight but may lack some advanced features.

README

@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)
  • isEmpty
  • size
  • toArray
  • clear
• Build
• License

Install

npm 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

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

import

import {
  PriorityQueue,
  MinPriorityQueue,
  MaxPriorityQueue,
  ICompare,
  IGetCompareValue,
} 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

interface ICar {
  year: number;
  price: number;
}

const compareCars: ICompare<ICar> = (a: ICar, b: ICar) => {
  if (a.year > b.year) {
    return -1;
  }
  if (a.year < b.year) {
    // prioritize newest cars
    return 1;
  }
  // with lowest price
  return a.price < b.price ? -1 : 1;
};

const carsQueue = new PriorityQueue<ICar>(compareCars);

JS

const carsQueue = new PriorityQueue((a, b) => {
    if (a.year > b.year) {
      return -1;
    }
    if (a.year < b.year) {
      // prioratize newest cars
      return 1;
    }
    // with lowest price
    return a.price < b.price ? -1 : 1;
  }
});

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

const numbersQueue = new MinPriorityQueue<number>();

interface IBid {
  id: number;
  value: number;
}
const getBidValue: IGetCompareValue<IBid> = (bid) => bid.value;
const bidsQueue = new MaxPriorityQueue<IBid>(getBidValue);

JS

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

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*log(n)) runtime.

PriorityQueue

TS

const numbers = [3, -2, 5, 0, -1, -5, 4];

const pq = PriorityQueue.fromArray<number>(numbers, (a, b) => a - b);

console.log(numbers); // [-5, -1, -2, 3, 0, 5, 4]
pq.dequeue(); // -5
pq.dequeue(); // -2
pq.dequeue(); // -1
console.log(numbers); // [ 0, 3, 4, 5 ]

JS

const numbers = [3, -2, 5, 0, -1, -5, 4];

const pq = PriorityQueue.fromArray(numbers, (a, b) => a - b);

console.log(numbers); // [-5, -1, -2, 3, 0, 5, 4]
pq.dequeue(); // -5
pq.dequeue(); // -2
pq.dequeue(); // -1
console.log(numbers); // [ 0, 3, 4, 5 ]

MinPriorityQueue, MaxPriorityQueue

TS

const numbers = [3, -2, 5, 0, -1, -5, 4];

const mpq = MaxPriorityQueue.fromArray<number>(numbers);

console.log(numbers); // [-5, -1, -2, 3, 0, 5, 4]
mpq.dequeue(); // 5
mpq.dequeue(); // 4
mpq.dequeue(); // 3
console.log(numbers); // [ 0, -1, -5, -2 ]

JS

const numbers = [3, -2, 5, 0, -1, -5, 4];

const mpq = MaxPriorityQueue.fromArray(numbers);

console.log(numbers); // [-5, -1, -2, 3, 0, 5, 4]
mpq.dequeue(); // 5
mpq.dequeue(); // 4
mpq.dequeue(); // 3
console.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.

const cars = [
  { year: 2013, price: 35000 },
  { year: 2010, price: 2000 },
  { year: 2013, price: 30000 },
  { year: 2017, price: 50000 },
  { year: 2013, price: 25000 },
  { year: 2015, price: 40000 },
  { year: 2022, price: 70000 }
];
cars.forEach((car) => carsQueue.enqueue(car));

const numbers = [3, -2, 5, 0, -1, -5, 4];
numbers.forEach((num) => numbersQueue.push(num)); // push is an alias for enqueue

const bids = [
  { id: 1, value: 1000 },
  { id: 2, value: 20000 },
  { id: 3, value: 1000 },
  { id: 4, value: 1500 },
  { id: 5, value: 12000 },
  { id: 6, value: 4000 },
  { id: 7, value: 8000 }
];
bids.forEach((bid) => bidsQueue.enqueue(bid));

front

peeks on the value with highest priority in the queue.

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

back

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

console.log(carsQueue.back()); // { year: 2010, price: 2000 }
console.log(numbersQueue.back()); // 5
console.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.

console.log(carsQueue.dequeue()); // { year: 2022, price: 70000 }
console.log(carsQueue.dequeue()); // { year: 2017, price: 50000 }
console.log(carsQueue.dequeue()); // { year: 2015, price: 40000 }

console.log(numbersQueue.dequeue()); // -5
console.log(numbersQueue.dequeue()); // -2
console.log(numbersQueue.dequeue()); // -1

console.log(bidsQueue.pop()); // { id: 2, value: 20000 }
console.log(bidsQueue.pop()); // { id: 5, value: 12000 }
console.log(bidsQueue.pop()); // { id: 7, value: 8000 }

isEmpty

checks if the queue is empty.

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

size

returns the number of elements in the queue.

console.log(carsQueue.size()); // 4
console.log(numbersQueue.size()); // 4
console.log(bidsQueue.size()); // 4

toArray

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

console.log(carsQueue.toArray());
/*
[
  { year: 2013, price: 25000 },
  { year: 2013, price: 30000 },
  { year: 2013, price: 35000 },
  { year: 2010, price: 2000 }
]
*/

console.log(numbersQueue.toArray()); // [ 0, 3, 4, 5 ]

console.log(bidsQueue.toArray());
/*
[
  { id: 6, value: 4000 },
  { id: 4, value: 1500 },
  { id: 3, value: 1000 },
  { id: 1, value: 1000 }
]
*/

clear

clears all elements in the queue.

carsQueue.clear();
console.log(carsQueue.size()); // 0
console.log(carsQueue.front()); // null
console.log(carsQueue.dequeue()); // null
console.log(carsQueue.isEmpty()); // true

numbersQueue.clear();
console.log(numbersQueue.size()); // 0
console.log(numbersQueue.front()); // null
console.log(numbersQueue.dequeue()); // null
console.log(numbersQueue.isEmpty()); // true

bidsQueue.clear();
console.log(bidsQueue.size()); // 0
console.log(bidsQueue.front()); // null
console.log(bidsQueue.dequeue()); // null
console.log(bidsQueue.isEmpty()); // true

Build

grunt build

License

The MIT License. Full License is here

Changelog

[6.1.1] - 2022-06-26

Fixed

• typos in readme.