High-performance priority queue with unique key constraint (O(1) lookup, O(log n) update)
npm install @llblab/uniqueueA high-performance priority queue with unique key constraint.
Combines a binary heap with a key-to-index Map, enabling O(log n) inserts/updates and O(1) lookups. Designed for leaderboard deduplication, task scheduling with updates, and LRU-like eviction scenarios.
- Unique Constraint: Ensures only one item per key exists in the queue.
- In-Place Updates: If an item with the same key is pushed, it updates the existing entry in-place (bubbling up or down as needed).
- O(1) Lookup: Tracks item positions internally, avoiding O(n) scans for updates.
- Max Size Eviction: Automatically removes the lowest-priority item when the limit is reached.
- Iterable: Supports for...of iteration over items.
- Zero Dependencies: ~1.7KB minified, ~0.7KB gzipped.
``bash`
npm install @llblab/uniqueue
`bash`
deno add jsr:@llblab/uniqueue
`javascript
import { Uniqueue } from "@llblab/uniqueue";
// The compare function determines which item sits at the root:
// - (a, b) => a - b → Min-heap (smallest at root, evicted first)
// - (a, b) => b - a → Max-heap (largest at root, evicted first)
//
// For "Top-N" scenario, use min-heap: when maxSize is exceeded,
// the root (smallest/worst) is evicted, keeping the best scores.
const leaderboard = new Uniqueue({
compare: (a, b) => a.score - b.score,
extractKey: (item) => item.playerId,
maxSize: 3,
});
// Add items
leaderboard.push({ playerId: "alice", score: 100 });
leaderboard.push({ playerId: "bob", score: 80 });
leaderboard.push({ playerId: "charlie", score: 120 });
console.log(leaderboard.peek());
// Output: { playerId: "bob", score: 80 } (min-heap root)
// Update existing item (alice improves score)
leaderboard.push({ playerId: "alice", score: 150 });
// Add item that exceeds maxSize
leaderboard.push({ playerId: "dave", score: 200 });
// Bob (lowest score at root) is evicted
leaderboard.snapshot();
// Contains charlie (120), alice (150), dave (200)
// Iterate over all items
for (const player of leaderboard) {
console.log(player.playerId, player.score);
}
`
Creates a new priority queue instance.
#### Options
| Option | Type | Default | Description |
| :----------- | :----------------- | :--------------------------------------- | :--------------------------------------------------------------------- |
| data | T[] | [] | Initial data array. |maxSize
| | number | Infinity | Maximum number of items. If exceeded, lowest priority item is evicted. |compare
| | (a, b) => number | (a, b) => (a < b ? -1 : a > b ? 1 : 0) | Comparison function for heap ordering. |extractKey
| | (item) => K | (item) => item | Function to extract unique key any type from item. |
#### push(item: T): T | undefined
Adds an item to the queue or updates an existing item with the same key.
- If the key is new: Adds item. If size > maxSize, removes and returns the evicted item.
- If the key exists: Updates the existing item and rebalances. Returns undefined.
#### pop(): T | undefined
Removes and returns the highest priority item (the root of the heap).
#### peek(): T | undefined
Returns the highest priority item without removing it.
#### remove(key: K): boolean
Removes the item with the given key. Returns true if removed, false otherwise.
#### has(key: K): boolean
Checks if an item with the given key exists.
#### get(key: K): T | undefined
Returns the item with the given key without removing it.
#### clear(): void
Removes all items from the queue.
#### size: number
Getter property that returns the number of items.
#### snapshot(): T[]
Returns a shallow copy of the underlying heap array. Safe for sorting or other mutations without affecting the queue.
#### [Symbol.iterator](): IterableIterator
Iterates over items in heap order (not sorted).
| Operation | Time Complexity |
| :-------------- | :-------------- |
| push (insert) | O(log n) |push
| (update) | O(log n) |pop
| | O(log n) |remove
| | O(log n) |peek
| / get | O(1) |has` | O(1) |
|
MIT