Class UpdatableBinaryHeapPriorityQueue<T>

A refinement of BinaryHeapPriorityQueue<T> which supports IUpdatablePriorityQueue<T> operations, such as retrieval and update of priorities and removal of items.

Inheritance
System.Object
BinaryHeapPriorityQueue<T>
UpdatableBinaryHeapPriorityQueue<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.BinaryHeap
Assembly: MoreStructures.dll
Syntax
public sealed class UpdatableBinaryHeapPriorityQueue<T> : BinaryHeapPriorityQueue<T>, IPeekKthPriorityQueue<T>, IMergeablePriorityQueue<T, BinaryHeapPriorityQueue<T>>, IUpdatablePriorityQueue<T>, IPriorityQueue<T>
Type Parameters
Name Description
T
Remarks

In order to support updates and deletions, two additional data structures are introduced:

  • a Item2PT, mapping items I of type T to BinaryHeapPriorityQueue<T> instances, containing values of type System.Int32, of MoreStructures.PriorityQueues.PrioritizedItem<T> instances containing I.
  • a PT2Idx from values to indexes of type System.Int32, into the backing list of the Binary Max Heap of this priority queue.

    Every time a request to remove or update an item I from the priority queue is made, Item2PT is used to retrieve all the values of MoreStructures.PriorityQueues.PrioritizedItem<T> instances with item.
    Those push timestamps can be multiple because the same item can be added multiple times to the queue.
    The push timestamps are organized themselves in per-item priority queues, with the same priority as the items in the main priority queue.
    This way, the push timestamp of highest priority for a given item can be peeked in constant time and extracted in logarithmic time.
    Once the timestamp of highest priority has been found, the corresponding index (if any) in the backing list of the Binary Max Heap of this priority queue can be found in constant time via the PT2Idx dictionary.
    Once the index is found, operations such as Remove(T) and UpdatePriority(T, Int32) can be executed in logarithmic time, since restoring heap properties after the modification of a single item of the heap requires a logarithmic number of sift down and/or sift up operations.

    The two dictionaries are kept up-to-date by implementing the extensibility points provided by BinaryHeapPriorityQueue<T>, after pushing, before popping and on items swapping.

Methods

| Improve this Doc View Source

Clear()

Declaration
public override void Clear()
Overrides
MoreStructures.PriorityQueues.BinaryHeap.BinaryHeapPriorityQueue<T>.Clear()
Remarks

Clears the underlying array list and the additional dictionaries introduced to support updates and deletions.
Time and Space Complexity is O(1).

| Improve this Doc View Source

GetPrioritiesOf(T)

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

ALGORITHM
- First, the priority queue of push timestamps for the provided item is retrieved from the dictionary of per-item queues of push timestamps.
- If such a queue is not found, item is not present in the main priority queue, and an empty sequence is returned.
- Otherwise, the queue is iterated over, getting the index corresponding to each timestamp extracted from the queue (where such index exists).
- The index is used to make a direct access to the corresponding MoreStructures.PriorityQueues.PrioritizedItem<T> in the list backing the main priority queue. The priority is taken from .

COMPLEXITY
- Retrieving the priority queue of push timestamps from the dictionary of per-item priority queues is a O(1) operation.
- Iterating such a priority queue requires duplicating the underlying data structure, which is a O(dup_factor) operation, where dup_factor is the average number of occurrences of an item in the data structure (1 means no duplicates, 2 means the item appears twice, etc.).
- Retrieving the index from the push timestamp and the priority from the MoreStructures.PriorityQueues.PrioritizedItem<T> instance are both constant-time operations.
- Therefore Time and Space Complexity are O(dup_factor).

| Improve this Doc View Source

RaiseItemPopping(Int32, Int32)

Invoked just before an item is removed from Items.

Declaration
protected override void RaiseItemPopping(int indexPopped, int indexInBufferArea)
Parameters
Type Name Description
System.Int32 indexPopped

The index of the item being popped.
When the heap is at the beginning of the list (which is the layout used by this queue), it is equal to 0.
System.Int32 indexInBufferArea

The index of the item of the last leaf, which is going to be swapped with the root during pop.
Overrides
MoreStructures.PriorityQueues.BinaryHeap.BinaryHeapPriorityQueue<T>.RaiseItemPopping(System.Int32, System.Int32)
| Improve this Doc View Source

RaiseItemPushed(Int32)

Invoked just after an item has been pushed into Items.

Declaration
protected override void RaiseItemPushed(int indexPushed)
Parameters
Type Name Description
System.Int32 indexPushed

The index of the item being pushed.
When the heap is at the beginning of the list (which is the layout used by this queue), it is equal to Count - 1 if the underlying list is fully utilized, and it's smaller than that otherwise (there is buffer at the end of the list, after the last item of the heap).
Overrides
MoreStructures.PriorityQueues.BinaryHeap.BinaryHeapPriorityQueue<T>.RaiseItemPushed(System.Int32)
| Improve this Doc View Source

RaiseItemsSwapped(Int32, Int32)

Invoked just after two items have been swapped of position in Items.

Declaration
protected override void RaiseItemsSwapped(int index1, int index2)
Parameters
Type Name Description
System.Int32 index1

The index of the first item swapped.
System.Int32 index2

The index of the second item swapped.
Overrides
MoreStructures.PriorityQueues.BinaryHeap.BinaryHeapPriorityQueue<T>.RaiseItemsSwapped(System.Int32, System.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

ALGORITHM
- The priority queue of push timestamps for the provided item is retrieved from the dictionary of per-item queues of push timestamps.
- If such a priority queue is not found, it means that item is not present in the main priority queue either. So, null is returned.
- If the priority queue is found, push timestamps are popped from it until the root of the priority queue contains a valid timestamp ts, i.e. a timestamp present in the dictionary mapping timestamps to indexes.
- If such a timestamp is not found, it means that that item used to be present in the main priority, but it is not anymore. So, null is returned.
- If such a timestamp is found, the backing list L for the main priority queue can be accessed via the index i, corresponding to the timestamp ts, simply by L[i]. L[i] represents the item to be removed.
- The priority of L[i] is set to the highest priority in the queue + 1 and the item is made sift up to the root, due to its new priority being the highest in the heap.
- Finally, the item, now at the root of the heap, is removed via a Pop().

COMPLEXITY
- Retrieving the priority queue associated with the item is a O(1) operation.
- Finding the right push timestamp may require a number of Pop() proportional to the number of times the priority of item has been changed.
- In the worst case, such number is equal to the number of insertion of item.
- Changing the priority of the MoreStructures.PriorityQueues.PrioritizedItem<T> to remove requires constant work.
- Sifting it up to the root and then popping it are both logarithmic in time and constant in space.
- Therefore, Time Complexity is O(log(n) + dup_factor) and Space Complexity is O(1), where dup_factor is the average number of occurrences of an item in the data structure (1 means no duplicates, 2 means the item appears twice, etc.).

| 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

ALGORITHM
- It first removes the provided item from the queue via Remove(T).
- Then, it pushes the same item with newPriority via Push(T, Int32).
- Finally it returns the MoreStructures.PriorityQueues.PrioritizedItem<T> removed in the first step.

COMPLEXITY
- Both Remove(T) and Push(T, Int32) have logarithmic Time Complexity and constant Space Complexity.
- Therefore, Time Complexity is O(log(n) + dup_factor) and Space Complexity is O(1), where dup_factor is the average number of occurrences of an item in the data structure (1 means no duplicates, 2 means the item appears twice, etc.).

Implements

IEnumerable<>

Extension Methods