Class ArrayListPriorityQueue<T>

An IPriorityQueue<T> implementation based on an unsorted list of its items. On top of basic operations it also supports IUpdatablePriorityQueue<T>, IPeekKthPriorityQueue<T> and IMergeablePriorityQueue<T, TPQTarget>. operations.

Inheritance
System.Object
ArrayListPriorityQueue<T>
Implements
IEnumerable<T>
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.PriorityQueues.ArrayList
Assembly: MoreStructures.dll
Syntax
public sealed class ArrayListPriorityQueue<T> : IUpdatablePriorityQueue<T>, IPeekKthPriorityQueue<T>, IMergeablePriorityQueue<T, ArrayListPriorityQueue<T>>, IPriorityQueue<T>
Type Parameters
Name Description
T

Remarks

ADVANTAGES AND DISADVANTAGES
This represents one of the simplest implementations of a Priority Queue.
It provides O(1) count and amortized insertion, at the cost of all other operations, which are O(n).
If insertion performance is the only highly critical operation, to the point that a constant time performance is the only acceptable runtime, and not even the logarithmic time insertion of a tree-based solution can be applied, this implementation may be the best choice, although lazy approaches such as FibonacciHeapPriorityQueue<T> can provide constant-time insertion performance, while keeping sub-linear complexity for all other operations.
If merging performance is also important, a solution based on linked lists can offer constant-time merging and still similar simplicity of implementation, same insertion performance and same tradeoff in terms of the complexity of all other operations.
When data extraction performance is also a concern, or the main concern, a more balanced solution in terms of complexity of its operations should be preferred.
This implementation can also be useful as a benchmark baseline in tests, when comparing against more complex solutions.

Constructors

| Improve this Doc View Source

ArrayListPriorityQueue()

Builds an empty priority queue.

Declaration
public ArrayListPriorityQueue()
| Improve this Doc View Source

ArrayListPriorityQueue(List<PrioritizedItem<T>>)

Builds a priority queue using the provided list as direct backing structure.

Declaration
public ArrayListPriorityQueue(List<PrioritizedItem<T>> items)
Parameters
Type Name Description
List<MoreStructures.PriorityQueues.PrioritizedItem<T>> items

The structure to be used as backing structure.
Remarks

The provided list is not copied over: it is used directly as backing structure for the queue.
Therefore, operations mutating the queue such as Push(T, Int32) will alter the content of the items list.

| Improve this Doc View Source

ArrayListPriorityQueue(IEnumerable<PrioritizedItem<T>>)

Builds a priority queue using the provided items to populate its backing structure.

Declaration
public ArrayListPriorityQueue(IEnumerable<PrioritizedItem<T>> items)
Parameters
Type Name Description
System.Collections.IEnumerable<MoreStructures.PriorityQueues.PrioritizedItem<T>> items

The items to be added to the queue.
Remarks

The provided sequence is enumerated and copied over onto a dedicated list: it is not used directly as backing structure for the queue.
Therefore, operations mutating the queue won't alter the provided items sequence.

Properties

| Improve this Doc View Source

Count

Declaration
public int Count { get; }
Property Value
Type Description
System.Int32
Remarks

Calls Count on the underlying list.
Time and Space Complexity are O(1).

Methods

| Improve this Doc View Source

Clear()

Declaration
public void Clear()
Remarks

Just clears the underlying array list.
Time and Space Complexity is O(1).

| Improve this Doc View Source

GetEnumerator()

Declaration
public IEnumerator<T> GetEnumerator()
Returns
Type Description
System.Collections.IEnumerator<T>
Remarks

Sorts the underlying list in descending order of priority and selects the items.
Time Complexity is O(n * log(n)) (when fully enumerated). Space Complexity is O(n), as required by sorting.

| Improve this Doc View Source

GetPrioritiesOf(T)

Declaration
public IEnumerable<int> GetPrioritiesOf(T item)
Parameters
Type Name Description
T item
Returns
Type Description
System.Collections.IEnumerable<System.Int32>
Remarks

Linearly scans the underlying list looking for MoreStructures.PriorityQueues.PrioritizedItem<T> having an item equals to the provided item (System.Object.Equals(System.Object, System.Object) is used to compare the two items of type T).
It then selects all priorities found for item and builds a ArrayListPriorityQueue<T> of System.Int32 values out of them.
Such a priority queue is returned as result.
Time Complexity is O(n * Teq) and Space Complexity is O(Seq), where Teq and Seq are the time and space cost of comparing two items of type T.

| Improve this Doc View Source

MergeFrom(ArrayListPriorityQueue<T>)

Declaration
public void MergeFrom(ArrayListPriorityQueue<T> targetPriorityQueue)
Parameters
Type Name Description
ArrayListPriorityQueue<T> targetPriorityQueue
Remarks

Just pushes all items in the targetPriorityQueue via Push(T, Int32), which appends each item to the end.
Then clears the content of the targetPriorityQueue, to respect the contract defined by IMergeablePriorityQueue<T, TPQTarget>.
Because the underlying structures of both source and target is an array list, there isn't an effective strategy for achieving sub-linear performance, and Push(T, Int32) gives the optimal linear performance.
Time and Space Complexity are O(m), where m is the number of items in the target.

| Improve this Doc View Source

Peek()

Declaration
public PrioritizedItem<T> Peek()
Returns
Type Description
MoreStructures.PriorityQueues.PrioritizedItem<T>
Remarks

Linearly scans the underlying list looking for the highest priority.
Time Complexity is O(n). Space Complexity is O(1).

| Improve this Doc View Source

PeekKth(Int32)

Declaration
public PrioritizedItem<T>? PeekKth(int k)
Parameters
Type Name Description
System.Int32 k
Returns
Type Description
System.Nullable<MoreStructures.PriorityQueues.PrioritizedItem<T>>
Remarks

Uses the Quick Select algorithm to find the k-th largest element by in the underlying list.
Because Quick Select requires at least partial in-place sorting, the entire content of the underlying list is first copied into a temporary list, which is passed as target to the Quick Select procedure.
Selected pivot is always at the end of the range of indexes in which selection is happening.
So If input is already sorted in ascending order, Time Complexity is O(n^2), whereas in the average case Time Complexity is O(n). Space Complexity is always O(n).

| Improve this Doc View Source

Pop()

Declaration
public PrioritizedItem<T> Pop()
Returns
Type Description
MoreStructures.PriorityQueues.PrioritizedItem<T>
Remarks

Linearly scans the underlying list looking for the index with the highest priority.
Then removes the item with such index from the underlying list and returns it as result.
Time Complexity is O(n). Space Complexity is O(1).

| Improve this Doc View Source

Push(T, Int32)

Declaration
public void Push(T item, int priority)
Parameters
Type Name Description
T item
System.Int32 priority
Remarks

Appends the provided item with its priority to the end of the underlying list.
Time Complexity is O(n). Space Complexity is O(1) (amortized over multiple executions of Push(T, Int32)).

| Improve this Doc View Source

Remove(T)

Declaration
public PrioritizedItem<T>? Remove(T item)
Parameters
Type Name Description
T item
Returns
Type Description
System.Nullable<MoreStructures.PriorityQueues.PrioritizedItem<T>>
Remarks

Linearly scans the underlying list looking for the index of the item equals to the provided item (System.Object.Equals(System.Object, System.Object) is used to compare the two items of type T).
If multiple occurrences of item are present with the same highest priority, the one with the lowest is selected, to guarantee stability.
If no such index is found, nothing is changed and null is returned.
Otherwise the item at such position is removed from the list and returned as result.
Time Complexity is O(n * Teq) and Space Complexity is O(Seq), where Teq and Seq are the time and space cost of comparing two items of type T.

| Improve this Doc View Source

UpdatePriority(T, Int32)

Declaration
public PrioritizedItem<T> UpdatePriority(T item, int newPriority)
Parameters
Type Name Description
T item
System.Int32 newPriority
Returns
Type Description
MoreStructures.PriorityQueues.PrioritizedItem<T>
Remarks

Linearly scans the underlying list looking for the index of the item equals to the provided item (System.Object.Equals(System.Object, System.Object) is used to compare the two items of type T) with the highest priority.
If multiple occurrences of item are present with the same highest priority, the one with the lowest is selected, to guarantee stability.
If no occurrence of item is found, a is raised.
Then replaces the MoreStructures.PriorityQueues.PrioritizedItem<T> at such index with a new one having same and , but set to newPriority.
Finally returns the previously stored MoreStructures.PriorityQueues.PrioritizedItem<T> at that index.
Time Complexity is O(n * Teq) and Space Complexity is O(Seq), where Teq and Seq are the time and space cost of comparing two items of type T.

Explicit Interface Implementations

| Improve this Doc View Source

IEnumerable.GetEnumerator()

Declaration
IEnumerator IEnumerable.GetEnumerator()
Returns
Type Description
System.Collections.IEnumerator
Remarks

Implements

IEnumerable<>

Extension Methods