Containers-PriorityQueue

A high-performance Priority Queue (Min-Heap) for Pharo. Engineered to provide $O(\log N)$ insertions and extractions while minimizing allocations during normal operations.

What is a Priority Queue?

Unlike a standard Queue (First-In-First-Out), a Priority Queue continuously self-sorts its elements so that the element with the highest priority (the minimum value, by default) is always instantly accessible at the front.

Standard sorting $O(N \log N)$ is too slow when data is constantly arriving and departing dynamically. CTPriorityQueue solves this using a Binary Min-Heap stored entirely within a flat, continuous array.

---

Loading

To install Containers-PriorityQueue, open the Playground (Ctrl + O + W) in your Pharo image and execute the following Metacello script (select it and press Do-it or Ctrl+D):

Metacello new
  baseline: 'ContainersPriorityQueue'
  repository: 'github://pharo-containers/Containers-PriorityQueue/src';
  load.

If you want to depend on it

Add the following snippet to your own Metacello baseline or configuration:

spec
  baseline: 'ContainersPriorityQueue'
  with: [ spec repository: 'github://pharo-containers/Containers-PriorityQueue/src' ].

---

Why use Containers-PriorityQueue?

When developing latency-sensitive systems such as graph pathfinding (Dijkstra), OS event loops, or robotics hardware schedulers, memory allocations trigger the Garbage Collector, freezing the application.

CTPriorityQueue is built to withstand these strict execution boundaries:

• Zero-Allocation Pipeline: By utilizing a flat array and pre-allocated capacities, supports millions of insertions and removals while avoiding additional allocations after capacity reservation.
• Algorithmic Guarantees:
  • Peek (first): $O(1)$
  • Insert (add:): $O(\log N)$
  • Extract (removeFirst): $O(\log N)$
• Polymorphic Sorting: By injecting a custom sortBlock:, the engine can be configured to behave as a Min-Heap, Max-Heap, or a custom scheduler comparing complex object properties (e.g., execution timestamps).

---

Basic Usage

Standard Min-Heap

"Initialize a queue. You can provide a capacity to prevent internal array growth"
queue := CTPriorityQueue new: 1000.

queue add: 50.
queue add: 10.
queue add: 30.

queue first.       "=> 10"
queue removeFirst. "=> 10"
queue size.        "=> 2"

Custom Sorting (Min-Heap vs Max-Heap)

CTPriorityQueue acts as a Min-Heap by default. You can easily inject a custom comparator using #sortBlock: to transform it into a Max-Heap or to sort complex objects.

Important Note: To prevent hidden $O(N)$ operations and preserve the strict $O(\log N)$ structural invariant, the sortBlock: must be configured before inserting any elements. Attempting to mutate the sorting rule on a non-empty queue will throw an explicit error.

pq := CTPriorityQueue new.
"Configure the rule before insertion"
pq sortBlock: [ :a :b | a > b ]. 

pq add: 10; add: 50.

Custom Object Scheduling (Event Loop / Robotics)

You can easily schedule complex objects or Associations by defining how the queue should sort them.

scheduler := CTPriorityQueue new.

"Define priority: Lower numbers equal higher urgency"
scheduler sortBlock: [ :a :b | a key <= b key ].

scheduler add: (5 -> 'Background Navigation Task').
scheduler add: (1 -> 'EMERGENCY BRAKE').
scheduler add: (3 -> 'Recalculate Route').

scheduler removeFirst value. "=> 'EMERGENCY BRAKE'"

---

Performance & Empirical Proof

To guarantee strictly bounded execution times, CTPriorityQueue avoids dynamic memory reallocation (Garbage Collection spikes) by supporting pre-allocated capacities and maintaining strict array-based binary trees.

1. The Dijkstra Refactor (Heap vs. Priority Queue)

We benchmarked CTPriorityQueue against the custom-built internal heap currently used in the graph-ai Dijkstra implementation.

Implementation	Execution Time	GC Penalty	Status
Custom Heap	133.337 ms	0.0 ms	Baseline
CTPriorityQueue	124.233 ms	0.0 ms	~5.8% Faster

Conclusion: While both implementations are strictly $O(\log N)$, CTPriorityQueue edges out the legacy script by a few milliseconds while replacing a one-off algorithm with a standard memory safe Pharo API.

2. Core Engine Stress Tests (1,000,000 Elements)

These tests isolate the core bubbleUp: and sinkDown: operations using a pre-allocated capacity of 1,000,000 elements to measure pure algorithmic overhead.

Workload	Operations	Time	GC Penalty
Insertion Stress	1M add:	132.7 ms	0 ms
Worst-Case Insert	1M descending add:	970.2 ms	0 ms
Extraction Stress	1M removeFirst	1,470.8 ms	0 ms

Conclusion: By completely eliminating the need for wrapped Node objects and utilizing a flat array, No measurable GC time was observed during these benchmarks.

3. Real-World Dynamic Simulations

These benchmarks simulate heavy, interleaved operations where the tree dynamically grows and shrinks, acting as a real-time interrupt scheduler.

Simulation	Scale	Execution Time	GC Penalty
Mixed Dijkstra Workload	500k cycles	2.65 s	14 ms (0.5%)
Robotics OS Scheduler	500k interrupts	3.20 s	94 ms (2.9%)

Conclusion: Even under a massive barrage of dynamic, randomized insertions and extractions (simulating unpredictable LIDAR interrupts and hardware emergency brakes), the engine executes millions of tree swaps in ~3 seconds, with the Garbage Collector accounting for less than 3% of the total execution time.

---

Contributing

This library is part of the Pharo Containers project. Contributions are welcome, whether implementing additional functional combinators, improving test coverage, or enhancing documentation. Please open an issue or pull request on GitHub.