Socket
Socket
Sign inDemoInstall

@datastructures-js/priority-queue

Package Overview
Dependencies
1
Maintainers
1
Versions
29
Alerts
File Explorer

Advanced tools

Install Socket

Detect and block malicious and high-risk dependencies

Install

@datastructures-js/priority-queue

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


Version published
Maintainers
1
Weekly downloads
56,304
decreased by-22.71%

Weekly downloads

Readme

Source

@datastructures-js/priority-queue

npm npm npm

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

NOTE: LeetCode is using previous versions of the lib here. I am maintaining v4 & v5 for this purpose
  • v4
  • v5

Contents (v6)

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

remove

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

carsQueue.remove((car) => car.price === 35000); // [{ year: 2013, price: 35000 }]

numbersQueue.remove((n) => n === 4); // [4]

bidsQueue.remove((bid) => bid.id === 3); // [{ id: 3, value: 1000 }]

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()); // 3
console.log(numbersQueue.size()); // 3
console.log(bidsQueue.size()); // 3

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: 2010, price: 2000 }
]
*/

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

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

Symbol.iterator

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

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

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

for (const bid of bidsQueue) {
  console.log(bid);
}
/*
{ id: 6, value: 4000 },
{ id: 4, value: 1500 },
{ id: 1, value: 1000 }
*/
console.log(bidsHeap.size()); // 0

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

Keywords

FAQs

Last updated on 23 Jan 2024

Did you know?

Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.

Install

Related posts

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc