Class ScyllaPriorityQueue<T>

High-performance priority queue backed by an array-based binary heap. By default this is a Min-heap (smallest item is highest priority), but Max-heap is also supported. Unsynchronized by default; use AsSynchronized(object) to obtain a thread-safe synchronized wrapper.

Inheritance

object

ScyllaPriorityQueue<T>

Implements

IScyllaCollection<T>

IScyllaCollection

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Namespace: Scylla.Core.Structures

Assembly: ScyllaCore.dll

Syntax

public sealed class ScyllaPriorityQueue<T> : IScyllaCollection<T>, IScyllaCollection

Type Parameters

Name	Description
T	The element type stored in the queue. May be any managed or value type. For DOTS/Burst usage, use ScyllaPriorityQueueDOTS<TValue> with an `unmanaged` type constraint.

Remarks

Priority is determined by the comparer provided at construction time (or Default when none is supplied). The heap always places the element with highest priority at index 0 (the root), so TryPeekTop(out T) and TryDequeue(out T) operate in O(1) and O(log n) time respectively. TryEnqueue(T) is O(log n).

For the common case of a simple integer priority on the item itself, implement IScyllaPriorityQueueItem on your item type and construct the queue with Default as the comparer.

The queue grows automatically when full unless fixedCapacity: true is passed at construction time. Growth doubles the backing buffer up to the maximum safe array length (0x7FEFFFFF).

This implementation is not thread-safe. Use AsSynchronized(object) or the builder's Synchronized(object) method to wrap it in a lock-based synchronized facade. For Burst/DOTS usage, see ScyllaPriorityQueueDOTS<TValue> instead.

// Direct construction - min-heap with fixed capacity
var queue = new ScyllaPriorityQueue<int>(capacity: 64, fixedCapacity: true, order: ScyllaPriorityQueueOrder.Min);
queue.TryEnqueue(5);
queue.TryEnqueue(1);
queue.TryEnqueue(3);
queue.TryDequeue(out var top); // top == 1
// Using fluent builder for complex configuration
var queue = ScyllaPriorityQueue<string>.CreateBuilder()
.WithCapacity(128)
.MaxHeap()
.WithComparer(StringComparer.OrdinalIgnoreCase)
.Synchronized()
.Build();
// Items implementing IScyllaPriorityQueueItem
var queue = new ScyllaPriorityQueue<MyTask>(
comparer: ScyllaPriorityQueueItemComparer<MyTask>.Default);

Constructors

ScyllaPriorityQueue(int, bool, ScyllaPriorityQueueOrder, IComparer<T>)

Initializes a new ScyllaPriorityQueue<T> with the specified configuration.

Declaration

public ScyllaPriorityQueue(int capacity = 4, bool fixedCapacity = false, ScyllaPriorityQueueOrder order = ScyllaPriorityQueueOrder.Min, IComparer<T> comparer = null)

Parameters

Type	Name	Description
int	capacity	Initial capacity of the backing heap array. Values less than 1 are silently clamped to 1. When `fixedCapacity` is `false`, this is only the starting capacity; the buffer grows on demand. When `fixedCapacity` is `true`, this is the permanent maximum capacity.
bool	fixedCapacity	When `true`, the queue will never grow beyond its initial capacity. TryEnqueue(T) returns `false` when the queue is full instead of resizing. When `false` (the default), the backing buffer doubles automatically when full.
ScyllaPriorityQueueOrder	order	Determines the heap ordering mode. Min (the default) dequeues the smallest element first; Max dequeues the largest first. Both modes use the same internal heap algorithms - the Max ordering is implemented by inverting comparisons in Scylla.Core.Structures.ScyllaPriorityQueue<T>.Compare(T, T).
IComparer<T>	comparer	The comparer used to order elements. When `null`, Default is used, which requires `T` to implement IComparable<T>. To order by an integer priority field on the item type, pass Default.

Properties

Capabilities

Gets the ScyllaCollectionCapabilities flags describing the optional operations supported by this priority queue instance.

Declaration

public ScyllaCollectionCapabilities Capabilities { get; }

Property Value

Type	Description
ScyllaCollectionCapabilities	Always includes HasCapacity, SupportsPeek, SupportsCopyTo, and SupportsContains.

Capacity

Gets the current capacity of the backing heap buffer.

Declaration

public int Capacity { get; }

Property Value

Type	Description
int	The length of the internal array. For fixed-capacity queues this is also the maximum number of elements the queue can hold. For dynamic queues this value increases as the buffer grows.

Count

Gets the number of elements currently stored in the priority queue.

Declaration

public int Count { get; }

Property Value

Type	Description
int	The number of elements in the heap, in the range `[0, Capacity]`.

IsEmpty

Gets a value indicating whether the priority queue contains no elements.

Declaration

public bool IsEmpty { get; }

Property Value

Type	Description
bool	`true` when Count is zero; otherwise `false`.

IsFixedCapacity

Gets a value indicating whether this priority queue has a fixed capacity that does not grow.

Declaration

public bool IsFixedCapacity { get; }

Property Value

Type	Description
bool	`true` if TryEnqueue(T) will return `false` when the queue is full rather than resizing the buffer; `false` if the buffer doubles automatically.

IsFull

Gets a value indicating whether the backing buffer is fully occupied.

Declaration

public bool IsFull { get; }

Property Value

Type	Description
bool	`true` when Count equals Capacity. For dynamic queues, a full state is transient because the next TryEnqueue(T) call grows the buffer. For fixed-capacity queues, this state means TryEnqueue(T) will return `false`.

SyncRoot

Gets the synchronization root for externally coordinating access to this collection.

Declaration

public object SyncRoot { get; }

Property Value

Type	Description
object	Always `null` for the unsynchronized queue. Use AsSynchronized(object) and then access SyncRoot on the resulting wrapper instead.

ThreadSafety

Gets the thread-safety guarantees provided by this priority queue.

Declaration

public ScyllaCollectionThreadSafety ThreadSafety { get; }

Property Value

Type	Description
ScyllaCollectionThreadSafety	Always Unsynchronized. Use AsSynchronized(object) to obtain a lock-based thread-safe wrapper.

Methods

AsSynchronized(object)

Creates and returns a ScyllaPriorityQueue<T>.SynchronizedScyllaPriorityQueue that wraps this queue and serializes all operations with a lock, making them safe for concurrent access from multiple threads.

Declaration

public ScyllaPriorityQueue<T>.SynchronizedScyllaPriorityQueue AsSynchronized(object syncRoot = null)

Parameters

Type	Name	Description
object	syncRoot	An optional external object to lock on. When `null` (the default), the wrapper allocates and owns a dedicated private lock object. Supply a custom sync root to share the lock across multiple synchronized collections that must be coordinated atomically.

Returns

Type	Description
ScyllaPriorityQueue<T>.SynchronizedScyllaPriorityQueue	A new ScyllaPriorityQueue<T>.SynchronizedScyllaPriorityQueue wrapping this queue instance.

Remarks

The returned wrapper holds a reference to this queue instance. Do not use the unwrapped queue concurrently after calling this method unless the caller manages external synchronization on the same syncRoot.

Clear()

Removes all elements from the priority queue, resetting Count to zero.

Declaration

public void Clear()

Remarks

For reference types, the backing buffer slots are explicitly set to null via Clear(Array, int, int) to release object references and allow the GC to collect them. For value types, only the count is reset (no array clearing needed) to avoid unnecessary work. The backing buffer is not resized; Capacity remains unchanged after this call.

Contains(T, IEqualityComparer<T>)

Determines whether the queue contains the specified item using a linear scan of the heap.

Declaration

public bool Contains(T item, IEqualityComparer<T> comparer = null)

Parameters

Type	Name	Description
T	item	The item to locate within the queue.
IEqualityComparer<T>	comparer	The equality comparer to use when testing each element. When `null`, Default is used, which uses IEquatable<T> when implemented and Equals(object) otherwise.

Returns

Type	Description
bool	`true` if `item` is found; `false` otherwise.

Remarks

Because the heap is not sorted in a way that supports sub-linear search by value, this operation must inspect every stored element in the worst case. Time complexity: O(n).

CopyTo(Span<T>)

Copies up to destination.Length elements from the queue into the provided span in heap internal order (not priority-sorted dequeue order).

Declaration

public int CopyTo(Span<T> destination)

Parameters

Type	Name	Description
Span<T>	destination	The span to write elements into. At most Count elements are written.

Returns

Type	Description
int	The number of elements actually copied, which is `min(Count, destination.Length)`.

Remarks

The copy reflects the heap's internal array layout. The element at index 0 is always the highest-priority item; remaining elements do not appear in sorted order.

CopyTo(T[], int)

Copies up to destination.Length - destinationIndex elements from the queue into the provided array, starting at destinationIndex, in heap internal order (not priority-sorted dequeue order).

Declaration

public int CopyTo(T[] destination, int destinationIndex)

Parameters

Type	Name	Description
T[]	destination	The target array. Must not be `null`.
int	destinationIndex	The zero-based index within `destination` at which to begin writing. Must be in the range `[0, destination.Length]`.

Returns

Type	Description
int	The number of elements actually copied.

Exceptions

Type	Condition
ArgumentNullException	Thrown when `destination` is `null`.
ArgumentOutOfRangeException	Thrown when `destinationIndex` is negative or greater than `destination.Length`.

CreateBuilder()

Creates a new fluent ScyllaPriorityQueue<T>.Builder for configuring and constructing a ScyllaPriorityQueue<T> instance.

Declaration

public static ScyllaPriorityQueue<T>.Builder CreateBuilder()

Returns

Type	Description
ScyllaPriorityQueue<T>.Builder	A fresh ScyllaPriorityQueue<T>.Builder instance with default settings (min-heap, capacity 4, dynamic growth).

Remarks

The builder provides a discoverable, named-parameter-style API for capacity, fixed-capacity mode, heap ordering, custom comparer, and optional synchronized wrapper creation. Prefer the builder over the constructor when multiple non-default options are needed, to avoid relying on positional arguments.

var queue = ScyllaPriorityQueue<int>.CreateBuilder()
    .WithCapacity(64)
    .MaxHeap()
    .FixedCapacity()
    .Build();

EnsureCapacity(int)

Ensures the priority queue backing buffer can hold at least minCapacity elements without a subsequent resize operation.

Declaration

public void EnsureCapacity(int minCapacity)

Parameters

Type	Name	Description
int	minCapacity	The minimum number of elements the buffer must be able to hold after this call. Values already satisfied by the current capacity are a no-op.

Remarks

If Capacity is already greater than or equal to minCapacity, this method returns immediately without allocating. Otherwise it delegates to Grow(int), which allocates a new buffer and copies all existing elements.

Exceptions

Type	Condition
InvalidOperationException	Thrown when this priority queue was constructed with `fixedCapacity: true` and the current capacity is insufficient. Fixed-capacity queues can never be resized.

GetEnumerator()

Returns an ScyllaPriorityQueue<T>.Enumerator that iterates through all elements in the queue in heap internal order (index 0 first, which is the highest-priority item).

Declaration

public ScyllaPriorityQueue<T>.Enumerator GetEnumerator()

Returns

Type	Description
ScyllaPriorityQueue<T>.Enumerator	A new ScyllaPriorityQueue<T>.Enumerator positioned before the first element.

Remarks

The enumerator is a value type (struct), so using foreach on the concrete ScyllaPriorityQueue<T> type is allocation-free. Iterating through an IScyllaCollection<T> reference will box the enumerator and cause a heap allocation.

The enumerator snapshots the element count at creation time; elements added or removed during iteration are not reflected. No exception is thrown on modification.

TryAdd(T)

Attempts to add an item to the priority queue. This method is the IScyllaCollection<T> bridge to TryEnqueue(T) and behaves identically.

Declaration

public bool TryAdd(T item)

Parameters

Type	Name	Description
T	item	The item to add.

Returns

Type	Description
bool	`true` if the item was successfully enqueued; `false` if the queue is fixed-capacity and full.

TryDequeue(out T)

Attempts to remove and return the highest-priority item from the priority queue.

Declaration

public bool TryDequeue(out T item)

Parameters

Type	Name	Description
T	item	When this method returns `true`, contains the dequeued highest-priority item. When this method returns `false` (empty queue), contains `default(T)`.

Returns

Type	Description
bool	`true` if an item was successfully dequeued; `false` if the queue is empty.

Remarks

The root element (index 0) is the highest-priority item. After removal, the last element is moved to the root and sifted downward via SiftDown(int) to restore the heap invariant. The slot vacated by the last element is cleared (set to default) to release references for reference types and avoid stale data. Time complexity: O(log n).

TryEnqueue(T)

Attempts to insert an item into the priority queue, placing it at its correct heap position.

Declaration

public bool TryEnqueue(T item)

Parameters

Type	Name	Description
T	item	The item to enqueue.

Returns

Type	Description
bool	`true` if the item was successfully enqueued; `false` if IsFixedCapacity is `true` and the queue is already full.

Remarks

The item is appended to the end of the heap array and then sifted upward via SiftUp(int) to restore the heap invariant. If the backing buffer is full and the queue is not fixed-capacity, the buffer is grown (doubled) before insertion. Time complexity: O(log n) amortized.

TryPeek(out T)

Attempts to peek at the highest-priority item without removing it. This method is the IScyllaCollection<T> bridge to TryPeekTop(out T) and behaves identically.

Declaration

public bool TryPeek(out T item)

Parameters

Type	Name	Description
T	item	When this method returns `true`, contains the top-priority item. When this method returns `false`, contains `default(T)`.

Returns

Type	Description
bool	`true` if an item was available; `false` if the queue is empty.

TryPeekTop(out T)

Attempts to read the highest-priority item at the root of the heap without removing it.

Declaration

public bool TryPeekTop(out T item)

Parameters

Type	Name	Description
T	item	When this method returns `true`, contains the highest-priority item (the root). When this method returns `false` (empty queue), contains `default(T)`.

Returns

Type	Description
bool	`true` if an item was available; `false` if the queue is empty.

Remarks

This is a non-destructive O(1) operation - the heap is not modified. The item remains in the queue and will be returned again by subsequent calls to TryPeekTop(out T) or TryDequeue(out T).