Class BinaryHeapPriorityQueue<T>
An IPriorityQueue<T> implementation based on a Binary Max Heap of its items. On top of basic operations it also supports IPeekKthPriorityQueue<T> and IMergeablePriorityQueue<T, TPQTarget>.
Implements
Inherited Members
Namespace: MoreStructures.PriorityQueues.BinaryHeap
Assembly: MoreStructures.dll
Syntax
public class BinaryHeapPriorityQueue<T> : IPeekKthPriorityQueue<T>, IMergeablePriorityQueue<T, BinaryHeapPriorityQueue<T>>, IPriorityQueue<T>Type Parameters
| Name | Description |
|---|---|
| T |
Remarks
ADVANTAGES AND DISADVANTAGES
- The Binary Max Heap is used to store items with their priorities, in a way that the item with max priority is
immediately retrievable (making Peek() a constant-time operation), and easily extractable (making
Pop() a logarithmic-time operation).
- This comes a cost of the Push(T, Int32) operation, which is O(1) in
ArrayListPriorityQueue<T> and becomes a logarithmic-time operation in this implementation.
- So this implementation can be considered as a balanced compromise between insertion and extraction, which
complexifies the underlying data structure and loses some performance in insertion to obtain all-around
logarithmic performance.
- Given the "exponentially better" runtime of logarithmic operations w.r.t. linear ones, such compromise makes
sense for most scenarios.
- Merging two Binary Max Heap structures, however, still requires linear time. If merging performance is
critical, a more advanced tree-based implementation, such as
BinomialHeapPriorityQueue<T>,
FibonacciHeapPriorityQueue<T> and their derivations, should be used instead.
BINARY MAX HEAP REPRESENTATION
- The Binary Max Heap used for items and priorities is backed by a complete Binary Tree, represented as an
Array List of its items.
- The root of the tree is always in position 0, its children in positions 1 and 2, grand-children in positions
3, 4, 5 and 6 (where 3 and 4 are children of 1 and 5 and 6 are children of 2), etc.
- This is the most space-efficient layout for a complete tree, which allows O(1) root access, parent-to-child
navigation and child-to-parent navigation, by performing simple indexing arithmetic.
- The underlying Binary Tree is complete, hence balanced: it's height h is Math.Floor(log(n, 2)), where n is
the number of nodes in the tree. For example a complete Binary Tree of 3 nodes has necessarily height 1,
whereas one of 4 nodes has to have height 2.
- While the Binary Tree is complete, it is non necessarily full, meaning that the last level may not be
entirely filled with leaves and the number of leaves at the last level may vary from 1 up to 2^(h + 1) - 1.
- All modification operations (such as Pop()) done on the Binary Max Heap ensure that the tree is
kept complete and balanced.
REPEATED ITEMS AND PRIORITIES
- Repeated items, as well as repeated priorities, are supported.
- The implementation is stable both for priorities and items.
- If two items I1 and I2 are pushed with the same priority P at times T1 and T2 with T1 < T2, when P becomes
the highest priority in the heap, I1 is popped out of the heap before I2 is.
- That also applies to the case where I1 and I2 are equal by value and different by reference.
- Stability is achieved by keeping a "push index", i.e. a System.Int32 counter set to 0 in the constructor
and incremented every time a new item is introduced in the queue via a Push(T, Int32).
- The push index is included in the heap item record, together with the item of type
T and its priority of type System.Int32.
- This way two heap item records I1 and I2 with the same priority I1.Priority and I2.Priority, and potentially
the same or equal items I1.Item and I2.Item, will necessarily differ by push index, I1.PushTimestamp and
I2.PushTimestamp.
- Therefore a total strict order can be imposed.
Constructors
| Improve this Doc View SourceBinaryHeapPriorityQueue()
Builds an empty priority queue.
Declaration
public BinaryHeapPriorityQueue()Remarks
The underlying data structure for priorities and items is initialized to an empty structure.
Therefore, Time and Space Complexity is O(1).
BinaryHeapPriorityQueue(BinaryHeapPriorityQueue<T>)
Builds a new priority queue with the same items of the provided source.
Declaration
protected BinaryHeapPriorityQueue(BinaryHeapPriorityQueue<T> source)Parameters
| Type | Name | Description |
|---|---|---|
| BinaryHeapPriorityQueue<T> | source | The BinaryHeapPriorityQueue<T> instance to use as a source of data. |
Remarks
The underlying data structure is shallow copied.
Because it is made of immutable records, a shallow-copy is enough to ensure that its mutation in
source won't affect the new priority queue or viceversa.
Because the data structure contain O(n) items, Time and Space Complexity are O(n), where n is the number of
items in source.
Properties
| Improve this Doc View SourceCount
Declaration
public virtual int Count { get; }Property Value
| Type | Description |
|---|---|
| System.Int32 |
Remarks
Checks the count of the underlying heap.
The size of the heap may be smaller than the size of the underlying list, if there is buffer at the end.
Time and Space Complexity are O(1).
CurrentPushTimestamp
A non-negative, zero-based, monotonically strictly increasing counter, incremented at every insertion into this data structure by a Push(T, Int32).
Declaration
protected int CurrentPushTimestamp { get; set; }Property Value
| Type | Description |
|---|---|
| System.Int32 |
Items
The wrapped
Declaration
protected BinaryHeapListWrapper<PrioritizedItem<T>> Items { get; }Property Value
| Type | Description |
|---|---|
| BinaryHeapListWrapper<MoreStructures.PriorityQueues.PrioritizedItem<T>> |
Methods
| Improve this Doc View SourceClear()
Declaration
public virtual void Clear()Remarks
Just clears the underlying array list.
The internal push timestamp counter is not reset, nor the era. Therefore, new pushes after the clear will
receive push timestamps strictly higher than the ones assigned to the items in the queue before the clear.
Time and Space Complexity are O(1).
GetEnumerator()
Declaration
public virtual IEnumerator<T> GetEnumerator()Returns
| Type | Description |
|---|---|
| System.Collections.IEnumerator<T> |
Remarks
In order to return items in heap order (i.e. the max at each step), it first copies this priority queue into a
second temporary queue, which can be mutated without affecting the state of this queue.
It then iterates over the copy, calling Pop() until it becomes empty.
Time Complexity is O(n * log(n)) (when fully enumerated), because a single Pop() on an complete
binary heap takes logarithmic time, and there are n items to be extracted.
Space Complexity is O(n), as a copy of this queue is required as auxiliary data structure to emit elements in
the right order of priority.
MergeFrom(BinaryHeapPriorityQueue<T>)
Declaration
public virtual void MergeFrom(BinaryHeapPriorityQueue<T> targetPriorityQueue)Parameters
| Type | Name | Description |
|---|---|---|
| BinaryHeapPriorityQueue<T> | targetPriorityQueue |
Remarks
ALGORITHM
- Pushing all items in the targetPriorityQueue via Push(T, Int32), would
result in O(m * log(m)) Time Complexity, where m is the number of items in the
targetPriorityQueue.
- Instead, each of the m items from the targetPriorityQueue is added to the underlying
array list of this queue, at the end.
- Then, the content of targetPriorityQueue is cleared, to respect the contract defined
by IMergeablePriorityQueue<T, TPQTarget>.
- Finally, the heap property is restored globally for all items in the underlying array list, by sifting
down all items in the first half of the list, proceeding backwards from the middle of the list to its
first item.
- Such global sift down is required for the first half of the items only, because the second half only
contains leaves of the tree, for which a sift down would do nothing (i.e. the heap property is already
satisfied).
COMPLEXITY
- Appending m items has a linear cost over m.
- Clearing the target only takes constant time.
- Restoring the heap property globally would seem to take n / 2 * log(n), where n is the total number of
items in this queue, after the merge: the number of items to sift down plus the cost of sifting down the
tree. That would give O(n * log(n)) complexity: not a real improvement over the naive approach of pushing
n items.
- However, the length of the path to sift down is not as big as the entire height of the tree. Instead, the
closer the starting node is to the leave, the smaller it becomes: leaves have sift down paths of length
0, their parent of length 1, etc., up to the root, which has sift down path of length equal to the height
of the tree.
- A key observation is that in a complete and full tree there are more leaves than all nodes in other
levels combined, and that applies to all levels w.r.t. all smaller levels.
- So, sift down will cost less for way more nodes, resulting in overall O(n) Time Complexity.
- Space Complexity is O(m), since m items are added to the list storing the items of this queue.
Peek()
Declaration
public virtual PrioritizedItem<T> Peek()Returns
| Type | Description |
|---|---|
| MoreStructures.PriorityQueues.PrioritizedItem<T> |
Remarks
Peeks the item with max priority from the root of the heap, if any.
That is located at index 0 in the underlying list, and can be accessed in constant-time.
Therefore, Time and Space Complexity are O(1).
PeekKth(Int32)
Declaration
public virtual PrioritizedItem<T>? PeekKth(int k)Parameters
| Type | Name | Description |
|---|---|---|
| System.Int32 | k |
Returns
| Type | Description |
|---|---|
| System.Nullable<MoreStructures.PriorityQueues.PrioritizedItem<T>> |
Remarks
ALGORITHM
- If k is negative, an
- If k is non-smaller than the Count, null is returned.
- If k is 0, Peek() is returned.
- Otherwise, the main algorithm loop is performed, at most k times.
- A dedicated BinaryHeapPriorityQueue<T> C of System.Int32 values is instantiated.
- The values of C are the indexes of the underlying list of this priority queue, and identify candidates
for the k-th largest item.
- Such candidates are sorted in C by priority and push timestamps, exactly in the same way they are
sorted in this priority queue.
- At the beginning only the root of the priority queue (i.e. index 0) is pushed to C.
- At each iteration the max of C is popped from C and its left and right children (if any) are pushed into
C.
- After k iterations, the Peek() of C gives the k-th
largest item.
- Notice that C cannot run short of candidates (due to lack of children), because of the preconditions
on k.
COMPLEXITY
- Checks on the value of k w.r.t. the size of this priority queue and direct access to
the underlying list, to return the final result once the index has been found, are both done in constant
time.
- Candidates queue instantiation and 1st push into it are also constant time operations.
- The main loop consist of k iterations.
- At each iteration 1 item is popped and 2 are pushed, so the candidates queue grows of 1 item per cycle.
- Each Pop() and Push(T, Int32) operation on the candidates queue has logarithmic
run, since they are done on a BinaryHeapPriorityQueue<T> instance.
- Therefore, Time Complexity is O(k * log(k)) and Space Complexity is O(k).
Pop()
Declaration
public virtual PrioritizedItem<T> Pop()Returns
| Type | Description |
|---|---|
| MoreStructures.PriorityQueues.PrioritizedItem<T> |
Remarks
ALGORITHM
- Peeks the first item from the heap and stores to return it as result.
- Takes the last item of the heap and moves to the root, in first position.
- Restores heap constraints by recursively sifting down new root, as many time as needed.
COMPLEXITY
- Peek() and removal of item with max priority and last leaf of the heap are all constant-time
operations.
- Since the heap is an complete binary tree, the heigh of the three is O(log(n)).
- So the number of "sift down" operations is logarithmic w.r.t. the input.
- Therefore, Time Complexity is O(log(n)) and Space Complexity is O(1), since modifications are all done
in-place in underlying data structures.
Push(T, Int32)
Declaration
public virtual void Push(T item, int priority)Parameters
| Type | Name | Description |
|---|---|---|
| T | item | |
| System.Int32 | priority |
Remarks
Negative priorities are supported.
ALGORITHM
- Adds a new leaf to the heap, carrying priority, item and unique push index.
- Restores heap constraints by recursively sifting up new leaf, as many time as needed.
COMPLEXITY
- Adding a new item with given priority and a leaf to the heap are constant-time operations.
- Since the heap is an complete binary tree, the heigh of the three is O(log(n)).
- So the number of "sift up" operations is logarithmic w.r.t. the input.
- Therefore, Time Complexity is O(log(n)) and Space Complexity is O(1), since modifications are all done
in-place in underlying data structure.
RaiseItemPopping(Int32, Int32)
Invoked just before an item is removed from Items.
Declaration
protected virtual void RaiseItemPopping(int indexPopped, int indexInBufferArea)Parameters
| Type | Name | Description |
|---|---|---|
| System.Int32 | indexPopped | The index of the item being popped.
|
| System.Int32 | indexInBufferArea | The index of the item of the last leaf, which is going to be swapped with the root during pop. |
RaiseItemPushed(Int32)
Invoked just after an item has been pushed into Items.
Declaration
protected virtual void RaiseItemPushed(int indexPushed)Parameters
| Type | Name | Description |
|---|---|---|
| System.Int32 | indexPushed | The index of the item being pushed.
|
RaiseItemsSwapped(Int32, Int32)
Invoked just after two items have been swapped of position in Items.
Declaration
protected virtual 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. |
Explicit Interface Implementations
| Improve this Doc View SourceIEnumerable.GetEnumerator()
Declaration
IEnumerator IEnumerable.GetEnumerator()Returns
| Type | Description |
|---|---|
| System.Collections.IEnumerator |