FlatQueue class final Collections

A very fast and tiny binary heap priority queue that stores (int, double).

Similar to HeapPriorityQueue<(int, double) but stores the queue as two flat lists, one for the items (32-bit integers) and their priority values (32-bit floats) respectively, and does not perform list compaction after removing elements unless compact is called manually.

Memory Allocation

In order to avoid thrashing spending main-thread time on performing list compaction, the queue does not compact itself after removing elements, retaining the (relatively cheap) int and double slots for future use. This means that on long-running algorithms, the queue may grow in size indefinitely, potentially causing memory issues, and should be discarded (to let the native memory be garbage collected) when no longer needed.

// Add 100 elements to a queue.
final queue = FlatQueue();
for (var i = 0; i < 100; i++) {
  queue.add(i, i.toDouble());
}

// Clear the queue, but the memory is still allocated.
queue.clear();
print(queue.length); // 0
print(queue.capacity); // 100

To manually free up memory without discarding, you can call compact:

final queue = FlatQueue();
for (var i = 0; i < 100; i++) {
  queue.add(i, i.toDouble());
}

queue.clear();
queue.compact();
print(queue.capacity); // 0

Performance

The performance of the queue is predictable for a binary heap:

• length: O(1)
• peek: O(1)
• pop: O(log n)
• add: O(log n)

When compared to HeapPriorityQueue<(int, double), it's approximately:

• ~2x faster to add elements;
• ~8x faster when removing elements.

That is a significant speed up if you can deal with the constraints of this queue.