Interface IMergeablePriorityQueue<T, TPQTarget>
An IPriorityQueue<T> which supports efficient merging of the items from a second
IMergeablePriorityQueue<T, TPQTarget> of type TPQTarget.
priority.
Inherited Members
Namespace: MoreStructures.PriorityQueues
Assembly: MoreStructures.dll
Syntax
public interface IMergeablePriorityQueue<T, in TPQTarget> : IPriorityQueue<T> where TPQTarget : IMergeablePriorityQueue<T, TPQTarget>Type Parameters
| Name | Description |
|---|---|
| T | |
| TPQTarget |
Remarks
ADVANTAGES AND DISADVANTAGES
- MergeFrom(TPQTarget) from a source S can be implemented in a general way by copying the entire target data
structure T and then performing m Pop(), where m is the number of items in T,
each followed by a Push(T, Int32) into S.
- This approach has the advantage of being general and not mutating the target structure when performing the
merge.
- It is, however, expensive both in time and space, having O(m * log(m)) Time and O(n) Space Complexity for
all known implementation of IPriorityQueue<T>.
- Implementing this interface can take advantage of the properties of the underlying data structure
implementing the priority queue, and providing better performance.
COMPLEXITY
- Notice that linear performance can be achieved by basic implementations of IPriorityQueue<T>,
such as ArrayListPriorityQueue<T>, by just concatenating the underlying data
structures.
- In cases such as BinaryHeapPriorityQueue<T>, after concatenating, heap constraints
have to be restored. However, this operation too, can be performed in linear time.
- An implementation based on linked lists would perform the merge in O(1) time, by just concatenating the two
underlying structures. That is a the cost of all subsequent operations on the queue.
- Implementations based on forest of heap trees can do it in O(log(n)) or even O(1), when lazy, and keep
logarithmic time for all operations on the resulting queue.
SIDE EFFECTS
- However, for sub-linear performance to be achieved, both with linked lists and forests of heaps, some form of
structure sharing between source and target is required, because replicating the content of the target
would take linear time.
- To avoid interferences between the queues after merge, the target is emptied out during merge.
- This is an operation which usually takes sub-linear time, so it doesn't affect the overall complexity of the
merge operation, and avoid post-merge side effects between the queues.
Methods
| Improve this Doc View SourceClear()
Clears this queue, wiping out all its items.
Declaration
void Clear()Remarks
Used by MergeFrom(TPQTarget) on the target IMergeablePriorityQueue<T, TPQTarget>.
MergeFrom(TPQTarget)
Merges all items the targetPriorityQueue into this priority queue, emptying out the content
of the targetPriorityQueue.
Declaration
void MergeFrom(TPQTarget targetPriorityQueue)Parameters
| Type | Name | Description |
|---|---|---|
| TPQTarget | targetPriorityQueue | The IMergeablePriorityQueue<T, TPQTarget>, to take the items from. |