Vanilla Priority Queue

A javascript implementation of a priority queue backed by a binary heap.


- Installation
- Usage
- API

Installation

``npm i vanilla-priority-queue --save`

Usage

`

const { MinPriorityQueue, MaxPriorityQueue } = require('vanilla-priority-queue');

let minPriorityQueue = new MinPriorityQueue();
/*
The insert operation takes an item and it's priority.
The item argument can be anything.
The priority argument must be provided as an integer value.
*/
minPriorityQueue.insert(3, 3);
minPriorityQueue.insert(10, 10);
minPriorityQueue.peek() // returns 3
minPriorityQueue.remove() // returns 3
minPriorityQueue.remove() // returns 10
minPriorityQueue.isEmpty() // returns true


let maxPriorityQueue = new MaxPriorityQueue();
maxPriorityQueue.insert(3, 3);
maxPriorityQueue.insert(10, 10);
maxPriorityQueue.peek() // returns 10
maxPriorityQueue.remove() // returns 10
maxPriorityQueue.remove() // returns 3
maxPriorityQueue.isEmpty() // returns true

`

API

Both the `MaxPriorityQueue` and `MinPriorityQueue` expose the following functions:

* peek()

Returns the highest priority item in the queue in constant time. For a `MaxPriorityQueue` this is the max element. For a `MinPriorityQueue` this is the min element.

* insert(item, priority)

The insert operation takes an `item` and it's `priority` and inserts the following object into the queue:

`
{
item: item,
priority: priority
}
`

The `item` argument can be anything.
The `priority` argument must be provided as an integer.

The operation completes in `O(lg n)` time.

* remove()

Removes the highest priority item in the queue in `O(lg n)` time. For a `MaxPriorityQueue` this is the max element. For a `MinPriorityQueue` this is the min element.

* isEmpty()

Returns a boolean value indicating whether the queue is empty or not.

* length()

Returns the length of the queue.

* getHeap()

Returns an array representation of the binary heap backing the priority queue. Note this contains a dummy `null` element at index `0``.