p-queue-ts
TypeScript icon, indicating that this package has built-in type declarations

1.0.3 • Public • Published

Priority Queue

A priority queue is a collection in which items can be added at any time, but the only item that can be removed is the one with the highest priority.

For more information, please check wiki.

codecov Build Status PRs Welcome License: MIT

Motivation

During practising some challenges in leetcode. I found this problem requires priority queue. So I decided to research some documentations online and try to implement by myself this lib. The result beats 97% in leetcode.

Installation

npm

npm i p-queue-ts

yarn

yarn add p-queue-ts

Usage

The priority queue lib uses max heap as a default way to build a queue.

import { PriorityQueue } from 'p-queue-ts';

Max priority queue

with array of numbers

const p = new PriorityQueue();
p.push(2);
p.push(7);
p.push(4);
p.push(1);
p.push(8);
p.push(1);

// The queue: [8, 7, 4, 1, 2, 1]

with array of objects

const p = new PriorityQueue(function (a, b) {
  return a.value < b.value;
});

p.push({ text: 'a', value: 2 });
p.push({ text: 'b', value: 7 });
p.push({ text: 'c', value: 4 });
p.push({ text: 'd', value: 1 });
p.push({ text: 'e', value: 8 });
p.push({ text: 'f', value: 1 });

/** The queue
[
  { text: 'e', value: 8 },
  { text: 'b', value: 7 },
  { text: 'c', value: 4 },
  { text: 'd', value: 1 },
  { text: 'a', value: 2 },
  { text: 'f', value: 1 },
]
 */

If you want to support min priority queue. The lib allows providing the customized comparator.

Min priority queue

with array of numbers

const p = new PriorityQueue(function (a, b) {
  return a > b;
});
p.push(2);
p.push(7);
p.push(4);
p.push(1);
p.push(8);
p.push(1);

// The queue: [1, 2, 1, 7, 8, 4]

with array of objects

const p = new PriorityQueue(function (a, b) {
  return a.value > b.value;
});

p.push({ text: 'a', value: 2 });
p.push({ text: 'b', value: 7 });
p.push({ text: 'c', value: 4 });
p.push({ text: 'd', value: 1 });
p.push({ text: 'e', value: 8 });
p.push({ text: 'f', value: 1 });

/** The queue
[
  { text: 'd', value: 1 },
  { text: 'a', value: 2 },
  { text: 'f', value: 1 },
  { text: 'b', value: 7 },
  { text: 'e', value: 8 },
  { text: 'c', value: 4 }
]
 */

API

push(value)

Add elements to queue

const p = new PriorityQueue();
p.push(1); // adding "1" to queue
p.push(2); // adding "2" to queue
p.push(3); // adding "3" to queue

// The queue: [3, 1, 2]

pop

Extract the largest or smallest element from the queue

const p = new PriorityQueue();
p.push(1); // adding "1" to queue
p.push(2); // adding "2" to queue
p.push(3); // adding "3" to queue

const elmenet = p.pop(); // Output: 3

The queue looks like this [2, 1]

top

Peek the element (get the largest or smallest element without removing it from queue)

const p = new PriorityQueue();
p.push(1); // adding "1" to queue
p.push(2); // adding "2" to queue
p.push(3); // adding "3" to queue

const elmenet = p.pop(); // Output: 3

// The queue is remained the same

size

Get the size of the queue

const p = new PriorityQueue();
p.push(1); // adding "1" to queue
p.push(2); // adding "2" to queue
p.push(3); // adding "3" to queue
p.push(4); // adding "4" to queue

const length = p.size(); // Output: 4

empty

Check whether the queue is empty or not.

  • true: if the queue is empty
  • false: if the queue has data

toArray

Extract queue to array

const p = new PriorityQueue();
p.push(1); // adding "1" to queue
p.push(2); // adding "2" to queue
p.push(3); // adding "3" to queue

const array = p.toArray(); // Output: [3, 1, 2]

Running time

You can check the performance of the package here: https://jsperf.com/p-queue-ts

Operation Binary heap
push O(lg n)
top O(1)
pop O(lg n)

Package Sidebar

Install

npm i p-queue-ts@1.0.3

Version

1.0.3

License

MIT

Unpacked Size

9.54 kB

Total Files

5

Last publish

Collaborators

  • dzungnguyen179