Fast Heap-based Priority Queue

Common errors

• TypeError: FastPriorityQueue is not a constructor

  cause This error typically occurs when attempting to instantiate `FastPriorityQueue` without the `new` keyword, or when importing it incorrectly as a named export in an ESM/TypeScript environment.
  fix Always instantiate the queue using `new FastPriorityQueue()`. For ESM/TypeScript, use `import FastPriorityQueue from 'fastpriorityqueue';`. For CommonJS, use `const FastPriorityQueue = require('fastpriorityqueue');`.

• ReferenceError: FastPriorityQueue is not defined

  cause The `fastpriorityqueue` module was either not installed, not imported/required correctly, or the variable name `FastPriorityQueue` was misspelled after import.
  fix First, ensure the package is installed: `npm install fastpriorityqueue`. Then, verify your import/require statement matches your module system (e.g., `import FastPriorityQueue from 'fastpriorityqueue';` for ESM/TypeScript or `const FastPriorityQueue = require('fastpriorityqueue');` for CommonJS).

• Elements are not sorted as expected / `peek()` returns an incorrect value.

  cause This usually indicates an issue with the custom comparator function (if provided) or that elements within the queue have been mutated externally, altering their priority without the queue being updated.
  fix Review your comparator function to ensure it correctly defines the priority (e.g., `(a, b) => a > b` for a max-heap, `(a, b) => a < b` or default for a min-heap). If using objects, ensure they are not mutated after being added to the queue; if their priority changes, remove and re-add them.

Warnings

• gotcha When providing a custom comparator function to the `FastPriorityQueue` constructor, ensure its logic correctly defines the desired priority. A common mistake is to reverse the comparison, leading to an improperly sorted queue. For a min-priority queue (smallest elements first), the default `(a, b) => a < b` or no comparator is used. For a max-priority queue, use `(a, b) => a > b`.
  Fix: Thoroughly test custom comparator functions with diverse data sets and edge cases to ensure the expected ordering. Remember that the comparator should return `true` if `a` has higher priority (comes before) `b`.
• gotcha Mutating objects that are already stored in the priority queue can lead to an inconsistent or incorrectly sorted queue state. The queue does not automatically detect external changes to element priorities and re-heapify. Operations like `peek()` and `poll()` will then return incorrect results.
  Fix: If an element's priority changes, it must be explicitly removed from the queue (`remove()` or `removeOne()`), its value updated, and then re-added (`add()`) to ensure the queue maintains its heap property. The `replaceTop()` method can be used if the mutated element was the top element.
• breaking Versions of `fastpriorityqueue` prior to `0.7.4` contained a bug related to the `kSmallest` exponent calculation. This bug could lead to incorrect results when utilizing features that depend on finding the k-smallest elements within the queue.
  Fix: Users relying on `kSmallest` functionality should upgrade to version `0.7.4` or newer to resolve this correctness issue and ensure accurate results.
• gotcha The `remove(value)` method uses the queue's internal comparator function to locate elements. This means it may not perform a strict identity comparison (`===`) but rather a comparison based on the defined priority. If multiple elements in the queue are considered 'equal' by the comparator, `remove(value)` might remove an arbitrary one of them, not necessarily a specific object instance.
  Fix: If precise removal of a specific object instance is required, use `removeOne(callback)` and provide a callback function that performs a strict identity check (e.g., `(item) => item === mySpecificObject`).
• gotcha After extensive `add()` and `poll()` operations (high churn), the underlying array used by the heap can accumulate unused memory slots. While not a functional error, failing to call `pq.trim()` periodically can lead to increased memory consumption, which might be critical in performance-sensitive or long-running applications.
  Fix: Consider calling `pq.trim()` after periods of significant queue modification to reclaim unused memory and optimize the heap's underlying storage.

Install

• npm install fastpriorityqueue npm
• yarn add fastpriorityqueue yarn
• pnpm add fastpriorityqueue pnpm

Imports

• FastPriorityQueue
  wrong:

  import { FastPriorityQueue } from 'fastpriorityqueue';

  correct:

  import FastPriorityQueue from 'fastpriorityqueue';

  The primary `FastPriorityQueue` class is a default export for ESM/TypeScript. Named imports using destructuring will result in an `undefined` value for `FastPriorityQueue`.
• FastPriorityQueue
  wrong:

  const { FastPriorityQueue } = require('fastpriorityqueue');

  correct:

  const FastPriorityQueue = require('fastpriorityqueue');

  For CommonJS environments, the `FastPriorityQueue` class is the module's default export. Attempting to destructure it as a named export will fail.
• FastPriorityQueue (Type)

  import type FastPriorityQueue from 'fastpriorityqueue';

  For TypeScript, it is good practice to explicitly import the type using `import type` if you only need the type definition, which can aid bundler optimizations.

Quickstart

This quickstart demonstrates the core functionality of FastPriorityQueue, including adding elements, peeking at the top element, checking the queue size, and polling elements. It also illustrates how to create a max-priority queue using a custom comparator function.

import FastPriorityQueue from 'fastpriorityqueue';

// Create a default min-priority queue
const pqMin = new FastPriorityQueue();
pqMin.add(1);
pqMin.add(0);
pqMin.add(5);
pqMin.add(4);
pqMin.add(3);

console.log('Min-Priority Queue - Peek:', pqMin.peek()); // Should return 0
console.log('Min-Priority Queue - Size:', pqMin.size); // Should return 5

// Create a max-priority queue using a custom comparator
const pqMax = new FastPriorityQueue(function(a, b) {
  return a > b; // Returns true if a has higher priority (is 'larger') than b
});
pqMax.add(1);
pqMax.add(0);
pqMax.add(5);
pqMax.add(4);
pqMax.add(3);

console.log('\nElements from Min-Priority Queue (poll):');
while (!pqMin.isEmpty()) {
  console.log(pqMin.poll()); // Will print 0 1 3 4 5
}

console.log('\nElements from Max-Priority Queue (poll):');
while (!pqMax.isEmpty()) {
  console.log(pqMax.poll()); // Will print 5 4 3 1 0
}

pqMin.trim(); // Optional: optimizes memory usage after churn