sorted-queue

sorted-queue

A sorted queue, based on an array-backed binary heap.

Installation

$ npm i sorted-queue

Usage

import { SortedQueue } from "sorted-queue";

const queue = new SortedQueue();

// `queue.push()` adds a value to the queue and returns an object
// `item` with the `item.value` set to the pushed value.
queue.push(1); // { value: 1, ... }
queue.push(-1); // { value: -1, ... }
queue.push(0); // { value: 0, ... }

// `queue.peek()` returns the item with the smallest value.
queue.peek().value; // -1

// `queue.pop()` returns the item with the smallest value
// and also removes it from the queue.
queue.pop().value; // -1
queue.pop().value; // 0
queue.pop().value; // 1

// `pop()` and `peek()` return `undefined` when the queue is empty
queue.pop(); // undefined
queue.peek(); // undefined

// `empty()` returns `true` when the queue is empty, `false` otherwise
queue.empty(); // true

// Items returned by push() can also be removed using `item.pop()`.
const first = queue.push(0);
const middle = queue.push(1);
const last = queue.push(2);

// `item.pop()` returns `true` if the item existed in the queue, and
// `false` if the item has already been removed previously.
middle.pop(); // true
middle.pop(); // false

// The order is preserved no matter from which position the item got
// removed from.
first.pop(); // true
queue.pop().value; // 2
queue.pop(); // undefined

// For more complex sortings you can defined a custom comparison function
// (with the same signature as the comparison function Array#sort takes).
const custom = new SortedQueue<{ name: string }>((a, b) =>
  a.name.localeCompare(b.name)
);
custom.push({ name: "Mallory" });
custom.push({ name: "Alice" });
custom.push({ name: "Bob" });
custom.pop().value; // { name: "Alice" }
custom.pop().value; // { name: "Bob" }
custom.pop().value; // { name: "Mallory" }

License

This library is licensed under the MIT license. See LICENSE.