@datastructures-js/priority-queue

@datastructures-js/priority-queue

A performant priority queue implementation using a Heap data structure.

Contents

• 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