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:

1. Virtually all elements use a one-dimensional array to maintain this heap.
2. The caller can customize the comparator, but the types must be consistent. If there is no comparator, the default comparator is used.
3. By default, a parent node has up to 4 child nodes. When D=4, the efficiency seems to be the best.
4. 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:

1. First, record the maximum index position of the current element and expand the capacity according to appropriate conditions.
2. Under normal circumstances, capacity expansion is twice the growth rate.
3. 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:

1. Return the root node element, then remove the root node element and adjust the heap.
2. 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.
3. 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.