PriorityQueue<TElement,TPriority>

基本容器

值元组数组保存着所有节点

1
2
3
4
/// <summary>
        /// Represents an implicit heap-ordered complete d-ary tree, stored as an array.
        /// </summary>
private (TElement Element, TPriority Priority)[] _nodes;

通常来讲优先级队列的逻辑结构由堆实现，而堆是一棵完全二叉树 ，但这里用的是一颗四叉树。

至于为什么，维基百写道🤭：wiki！

所以这里父子节点索引关系是：
$$
(son-1)>>2=daddy\
(daddy<<2)+1=firstSon
$$

构造方法

构造方法共有六，区别就在于有无初始容量，比较器，迭代器

  • 若初始容量未传参，则调用Array.Empty返回空数组
  • 传入迭代器则迭代循环赋值
  • 无比较器传参，指定默认TPriority比较器，，同时字段_comparer赋值null，表示使用默认比较器

常用方法

  • ```c#
    void Enqueue(TElement element, TPriority priority)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11

      1. 首先检查容量大小，如果当前长度和容量相同则调用``void Grow(int minCapacity)``扩容

         扩容系数未2，最小扩容长度为4

      2. 根据是否使用默认比较器调用对应的向上堆排序方法

         ``void MoveUpDefaultComparer((TElement Element, TPriority Priority) node, int nodeIndex)``  

    - ```c#
      TElement Dequeue()

    1. 取首元素和最后一个元素LastNode

    2. 向下堆排序具体操作如下

      • while ((i = GetFirstChildIndex(nodeIndex)) < size)
{
    // Find the child node with the minimal priority
    (TElement Element, TPriority Priority) minChild = nodes[i];
    int minChildIndex = i;

    int childIndexUpperBound = Math.Min(i + Arity, size);
    while (++i < childIndexUpperBound)
    {
        (TElement Element, TPriority Priority) nextChild = nodes[i];
        if (Comparer<TPriority>.Default.Compare(nextChild.Priority, minChild.Priority) < 0)
        {
            minChild = nextChild;
            minChildIndex = i;
        }
    }

    // Heap property is satisfied; insert node in this location.
    if (Comparer<TPriority>.Default.Compare(node.Priority, minChild.Priority) <= 0)
    {
        break;
    }

    // Move the minimal child up by one node and
    // continue recursively from its location.
    nodes[nodeIndex] = minChild;
    nodeIndex = minChildIndex;
}

        两层嵌套循环，

        第一层循环是从父节点的第一个子节点开始，终止条件是索引超过现有长度，或者LastNode优先级小于等于当前节点优先级

        第二次循环时子节点的循环，取得其最小优先级节点minChild后循环结束，此时判断LastNode优先级是否小于等于minChild优先级，若是break，若不是赋值父节点为minChild,同时选取minChild的索引为第一层循环的nodeindex

        循环结束后，将当前节点赋值为LastNode，LastNode置为默认值。

    3. 其他方法大多异曲同工.