Priority Queue for Pharo
# Containers-PriorityQueue
A dynamically **Indexed Priority Queue** providing guaranteed $O(\log N)$ operations and $O(1)$ internal lookups. Engineered to eliminate linear scanning bottlenecks during dynamic priority updates, enabling safe, high-performance graph processing and event scheduling.
 
## What is an Indexed Priority Queue?
A standard Priority Queue (or Heap) is excellent for batch insertions and sequential popping. However, if you need to mutate the priority of an element *already sitting deep inside the queue* (e.g., relaxing an edge in Dijkstra's algorithm), a standard Heap forces an $O(N)$ linear scan just to find the element before it can sift it.
**Our Priority Queue** solves this by bridging a complete binary tree with an internal **$O(1)$ Identity Map**.
Every element's exact topological coordinate in the backing array is tracked in real-time. When a priority changes, the queue locates the item instantly in $O(1)$ and restores the heap invariant in strict $O(\log N)$ time.
Furthermore, it guarantees **Stable FIFO Tie-Breaking**. Elements inserted with identical priorities are strictly dequeued in the exact order they arrived, managed transparently via monotonic insertion counters.
## Loading
To install `Containers-PriorityQueue`, open the Playground (`Ctrl + O + W`) in your Pharo image and execute the following Metacello script:
```smalltalk
Metacello new
baseline: 'ContainersPriorityQueue';
repository: 'github://pharo-containers/Containers-PriorityQueue/src';
load.
```
## Why use Containers-PriorityQueue?
Standard Heaps execute incredibly fast batch operations but structurally collapse under dynamic graph workloads. `Containers-PriorityQueue` pays a slight architectural tax on raw inserts to maintain its index map and wrapper objects, but in return, it completely eliminates the $O(N)$ mutation bottleneck.
| Operation | Pharo Standard `Heap` | `CTPriorityQueue` (Indexed) |
| :--- | :--- | :--- |
| **Insert** | $O(\log N)$ | $O(\log N)$ |
| **Pop** | $O(\log N)$ | $O(\log N)$ |
| **Peek** | $O(1)$ | $O(1)$ |
| **Change Priority** | $O(N)$ linear scan + $O(N)$ shift | **$O(1)$ lookup + $O(\log N)$ sift** |
| **Stable FIFO Ties** | ❌ Lost / Arbitrary | ✅ **Guaranteed** |
### Key Benefits
* **$O(\log N)$ Dynamic Updates:** Mid-queue priority mutations execute instantly without scanning the array.
* **Stable Sorting:** Elements with equal priorities are strictly ordered by arrival time.
## Basic Usage
```smalltalk
"Create a new Priority Queue (Min Heap by default)"
queue := CTPriorityQueue new.
"Insert elements with explicit priorities"
queue insert: 'Background Task' withPriority: 50.
queue insert: 'UI Render' withPriority: 20.
queue insert: 'Network Call' withPriority: 30.
"Non destructive peek"
queue peek. "=> 'UI Render'"
"Dynamically mutate priority deep in the queue in O(log N)"
queue changePriorityOf: 'Background Task' to: 5.
"Dequeue elements in strict priority order"
queue pop. "=> 'Background Task' (Elevated to top)"
queue pop. "=> 'UI Render'"
"Custom Sort Blocks for Max Heap configuration"
maxQueue := CTPriorityQueue new sortBlock: [ :a :b | a > b ].
maxQueue insert: 'Low' withPriority: 1.
maxQueue insert: 'High' withPriority: 100.
maxQueue pop. "=> 'High'"
```
## Performance & Empirical Proof
To validate the theoretical architecture, this structure was stress-tested against Pharo's standard `Heap` using an adversarial workload simulating Dijkstra's path-relaxation (continuous mid-queue priority updates).
By eliminating the $O(N)$ lookup bottleneck, `CTPriorityQueue` maintained flat, single-digit millisecond execution times while the baseline implementation suffered from catastrophic UI-thread locking.
### Benchmark Results (Dynamic Priority Updates)
| Graph Size | Priority Updates | `CTPriorityQueue` | Pharo Standard `Heap` | Relative Performance |
| :--- | :--- | :--- | :--- | :--- |
| $N = 10,000$ | 5,000 | **6 ms** | 1,571 ms | **~261x faster** |
| $N = 10,000$ | 10,000 | **14 ms** | 3,502 ms | **~250x faster** |
| $N = 100,000$ | 10,000 | **64 ms** | 34,014 ms | **~531x faster** |
### Reproducing the Benchmarks: The Dijkstra Simulation
Standard arrays and unmapped heaps often perform well on simple batch insertions. However, they structurally collapse under the requirements of advanced graph processing (e.g., Dijkstra's or A* algorithms) and dynamic event schedulers.
In a pathfinding scenario, a node is initially enqueued with an infinite (or very high) cost. As the algorithm explores the graph, it constantly discovers shorter paths and must **relax** (decrease) the priority of existing nodes already sitting deep inside the queue.
Because Pharo's standard `Heap` lacks an internal index map, relaxing a priority forces an $O(N)$ linear scan to find the node, an $O(N)$ array-shift to remove it, and a final re-insertion. `CTPriorityQueue` utilizes an internal `IdentityDictionary` to locate the node in $O(1)$ and sifts it in strict $O(\log N)$.
You can reproduce the 530x performance multiplier yourself by executing the following adversarial workload in your Pharo Playground. It simulates 10,000 nodes undergoing 5,000 dynamic mid-queue priority relaxations:
```smalltalk
| numNodes numUpdates myQueue standardHeap nodes myTime heapTime randomTargets newPriorities |
numNodes := 10000.
numUpdates := 5000.
"PREPARE workloads and target nodes to guarantee a fair benchmark"
nodes := (1 to: numNodes) collect: [ :i | 'Node', i printString ].
randomTargets := (1 to: numUpdates) collect: [ :i | nodes atRandom ].
newPriorities := (1 to: numUpdates) collect: [ :i | 100 atRandom ]. "Simulating path relaxation"
"--- Our Priority Queue ---"
myQueue := CTPriorityQueue new.
"Initial Enqueue (Simulating Infinite Cost)"
nodes do: [ :n | myQueue insert: n withPriority: 10000 ].
myTime := [
1 to: numUpdates do: [ :i |
"O(1) lookup + O(log N) sift"
myQueue changePriorityOf: (randomTargets at: i) to: (newPriorities at: i).
].
] timeToRun.
"--- Pharo Standard Heap ---"
"We must use Associations to track values and priorities in a standard Heap"
standardHeap := Heap sortBlock: [ :a :b | a value < b value ].
nodes do: [ :n | standardHeap add: (Association key: n value: 10000) ].
heapTime := [
| targetNode newP targetAssoc |
1 to: numUpdates do: [ :i |
targetNode := randomTargets at: i.
newP := newPriorities at: i.
"O(N)"
targetAssoc := standardHeap detect: [ :assoc | assoc key = targetNode ].
"O(N)"
standardHeap remove: targetAssoc.
"Re-insertion"
standardHeap add: (Association key: targetNode value: newP).
].
] timeToRun.
"--- RESULTS ---"
{
'1. CTPriorityQueue (5k Dynamic Updates)' -> myTime.
'2. Pharo Heap (5k Dynamic Updates)' -> heapTime.
} inspect.
```
### Technical Analysis
* **The $O(N)$ Collapse:** The 34-second execution time for the standard `Heap` at $N = 100,000$ proves that relying on linear `detect:` and `remove:` operations fundamentally breaks under heavy event-sourcing or graph-traversal loads.
* **Constant-Time Mapping:** The 64ms clear by `CTPriorityQueue` empirically proves the efficiency of the internal `IdentityDictionary`. Looking up the exact array index of a target node bypasses the CPU cache misses associated with array scanning.