Package Exports
- @datastructures-js/priority-queue
- @datastructures-js/priority-queue/index.js
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 heap-based implementation of priority queue in javascript with typescript support.
Contents
Install
npm install --save @datastructures-js/priority-queueAPI
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()); // falsesize
returns the number of elements in the queue.
console.log(carsQueue.size()); // 4
console.log(numbersQueue.size()); // 4
console.log(bidsQueue.size()); // 4toArray
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()); // trueBuild
grunt buildLicense
The MIT License. Full License is here