## preface

Some time ago, I saw a big man right net 6.0, but there was no source code analysis, so I looked at it and shared it with the mentality of exploring the source code. It is not like ordinary queue first in first out (FIFO), but out of the queue according to priority.

ps: readers should pay more attention to the comments of the code.

## Understanding of D-ary tree (d-ary heap)

First, when we represent a heap (large top heap or small top heap), we actually maintain a binary tree through a one-dimensional array (d=2,d indicates that each parent node has at most several child nodes). First, look at the binary tree in the following figure, and the number represents the index:

- The index of the parent node of any node is: (index - 1) / d
- The index of the left child node of any node is: (index * d) + 1
- The index of the right child node of any node is: (index * d) + 2
- Its time complexity is O(logndn)

Through the above formula, we can easily express a heap through an array, and we can quickly insert and delete as long as we can get the correct index.

## Source code analysis

### Construct initialization

This section mainly introduces the key fields and methods, comparator initialization and heap initialization. Please see the following code:

public class PriorityQueue<TElement, TPriority> { /// <summary> ///Save a one-dimensional array of all nodes, and each item is a tuple /// </summary> private (TElement Element, TPriority Priority)[] _nodes; /// <summary> ///Priority comparator, a generic type used here, can be implemented by itself /// </summary> private readonly IComparer<TPriority>? _comparer; /// <summary> ///Current heap size /// </summary> private int _size; /// <summary> ///Version number /// </summary> private int _version; /// <summary> ///It means that the parent node has at most 4 child nodes, that is, d = 4 (the efficiency seems to be the highest when d = 4) /// </summary> private const int Arity = 4; /// <summary> ///Bitwise operators are used to shift 2 left or 2 right (more efficient), which is equivalent to dividing by 4, /// </summary> private const int Log2Arity = 2; /// <summary> ///Constructor initializes the heap and comparator /// </summary> public PriorityQueue() { _nodes = Array.Empty<(TElement, TPriority)>(); _comparer = InitializeComparer(null); } /// <summary> ///Overload the constructor to define the comparator, otherwise use the default comparator /// </param> public PriorityQueue(IComparer<TPriority>? comparer) { _nodes = Array.Empty<(TElement, TPriority)>(); _comparer = InitializeComparer(comparer); } private static IComparer<TPriority>? InitializeComparer(IComparer<TPriority>? comparer) { //If it is a value type, null is returned if it is a default comparator if (typeof(TPriority).IsValueType) { if (comparer == Comparer<TPriority>.Default) { return null; } return comparer; } //Otherwise, use a custom comparator else { return comparer ?? Comparer<TPriority>.Default; } } /// <summary> ///Gets the parent node of the index /// </summary> private int GetParentIndex(int index) => (index - 1) >> Log2Arity; /// <summary> ///Gets the left child node of the index /// </summary> private int GetFirstChildIndex(int index) => (index << Log2Arity) + 1; }

Unit summary:

- Virtually all elements use a one-dimensional array to maintain this heap.
- The caller can customize the comparator, but the types must be consistent. If there is no comparator, the default comparator is used.
- By default, a parent node has up to 4 child nodes. When D=4, the efficiency seems to be the best.
- The bit operator is used to obtain the index position of the parent node and the index position of the child node, which is more efficient.

### Queue operation

The queue joining operation is relatively simple, mainly for capacity expansion and insertion. Please see the following code:

public void Enqueue(TElement element, TPriority priority) { //Get the index of the maximum position, and then add the array length + 1 int currentSize = _size++; _version++; //If the length is equal, it indicates that the maximum position has been reached, and the array needs to be expanded to accommodate more elements if (_nodes.Length == currentSize) { //For capacity expansion, the parameter represents the minimum capacity of the array Grow(currentSize + 1); } if (_comparer == null) { MoveUpDefaultComparer((element, priority), currentSize); } else { MoveUpCustomComparer((element, priority), currentSize); } } private void Grow(int minCapacity) { //Growth multiple const int GrowFactor = 2; //Minimum value of each expansion const int MinimumGrow = 4; //2X expansion for each expansion int newcapacity = GrowFactor * _nodes.Length; //The array cannot be greater than the maximum length if ((uint)newcapacity > Array.MaxLength) newcapacity = Array.MaxLength; //Use the maximum of both of them newcapacity = Math.Max(newcapacity, _nodes.Length + MinimumGrow); //If smaller than the parameter, the minimum value of the parameter is used if (newcapacity < minCapacity) newcapacity = minCapacity; //Reallocate memory and set the size, because the storage of the array is continuous in memory Array.Resize(ref _nodes, newcapacity); } private void MoveUpDefaultComparer((TElement Element, TPriority Priority) node, int nodeIndex) { //nodes save copy (TElement Element, TPriority Priority)[] nodes = _nodes; //Here, the queue operation starts from the first position of the free index while (nodeIndex > 0) { //Find parent node index location int parentIndex = GetParentIndex(nodeIndex); (TElement Element, TPriority Priority) parent = nodes[parentIndex]; //The inserted node is compared with the parent node. If it is less than 0 (the small top heap built under the default comparator), the position is exchanged if (Comparer<TPriority>.Default.Compare(node.Priority, parent.Priority) < 0) { nodes[nodeIndex] = parent; nodeIndex = parentIndex; } //It can be regarded as performance optimization. There is no need to check all nodes. When it is found that it is greater than, just exit directly else { break; } } //Put the insertion node where it should be nodes[nodeIndex] = node; }

Unit summary:

- First, record the maximum index position of the current element and expand the capacity according to appropriate conditions.
- Under normal circumstances, capacity expansion is twice the growth rate.
- When inserting data, look up or down from the parent node of the last node, compare the Priority of elements and exchange positions, and build a small top heap by default.

### Out of line operation

The out of queue operation is simply to return and remove the root element (that is, the first element of the array), and then place the smallest or largest element on the top of the heap according to the comparator. See the following code:

public TElement Dequeue() { if (_size == 0) { throw new InvalidOperationException(SR.InvalidOperation_EmptyQueue); } //Returns the top of heap element TElement element = _nodes[0].Element; //Then adjust the heap. RemoveRootNode(); return element; } private void RemoveRootNode() { //Record the index position of the last element and set the heap size to - 1 int lastNodeIndex = --_size; _version++; if (lastNodeIndex > 0) { //The size of the heap has been reduced by 1, so take the last element as a copy and start reorganizing the heap from the top of the heap (TElement Element, TPriority Priority) lastNode = _nodes[lastNodeIndex]; if (_comparer == null) { MoveDownDefaultComparer(lastNode, 0); } else { MoveDownCustomComparer(lastNode, 0); } } if (RuntimeHelpers.IsReferenceOrContainsReferences<(TElement, TPriority)>()) { //Set the element at the last position as the default _nodes[lastNodeIndex] = default; } } private void MoveDownDefaultComparer((TElement Element, TPriority Priority) node, int nodeIndex) { (TElement Element, TPriority Priority)[] nodes = _nodes; //The actual size of the heap int size = _size; int i; //When the index of the left child node is less than the actual size of the heap while ((i = GetFirstChildIndex(nodeIndex)) < size) { //Left child node element (TElement Element, TPriority Priority) minChild = nodes[i]; //Index of the current left child node int minChildIndex = i; //Here, all the adjacent child nodes of the same parent node are found, but it is necessary to judge whether the total size is exceeded int childIndexUpperBound = Math.Min(i + Arity, size); //Search according to the index interval order, and find the smallest child element position according to the comparator while (++i < childIndexUpperBound) { (TElement Element, TPriority Priority) nextChild = nodes[i]; if (Comparer<TPriority>.Default.Compare(nextChild.Priority, minChild.Priority) < 0) { minChild = nextChild; minChildIndex = i; } } //If the element of the last node is smaller than the smallest element, it can be placed directly on the parent node if (Comparer<TPriority>.Default.Compare(node.Priority, minChild.Priority) <= 0) { break; } //Assign the smallest child element to the parent node nodes[nodeIndex] = minChild; nodeIndex = minChildIndex; } //Put the last node in the free index position nodes[nodeIndex] = node; }

Unit summary:

- Return the root node element, then remove the root node element and adjust the heap.
- Starting from the root node, find all the child nodes of the corresponding parent node in turn and put them at the top of the heap, that is, the position of array index 0. Then, if there are still layers in the tree, continue the circular search.
- Put the last element in the appropriate position on the heap, and then set the element in the last position as the default value.

## summary

Through the interpretation of the source code, we not only understand the design of classes, but also have a deeper and clearer understanding of the implementation of priority queue data structure.

Here is only the main code pasted. Please see the detailed code click here , the author may have some misunderstandings. Please comment and correct.