开源优先队列FastPriorityQueue源码阅读

FastPriorityQueue

  源码连接：

https://github.com/BlueRaja/High-Speed-Priority-Queue-for-C-Sharp  

  大致结构：

  1节点在内存中的结构还是数组，且首节点为无意义节点，有效节点从索引1开始。（见FastPriorityQueue的T[] _nodes）
  2维护的节点必须时固定的继承。（见FastPriorityQueueNode）
  3该队列为非线程安全的
  4不要对不在优先级队列中的节点调用UpdatePriority（），也不要对在优先级队列的节点调用Enqueue（）。
  5一个节点只能在一个queue里面，如果要迁移节点到新的队列时应该先将其从原本的queue中移除并重置自身（ResetNode函数）后再加入新queue。

  如何实现判断界定是否在容器中。

  节点FastPriorityQueueNode中维护了一个数组的索引（见FastPriorityQueueNode的QueueIndex），该索引从1开始。
时间复杂度为O(1)。

  是否支持优先级动态变，变更后，如何排序?

  支持优先级动态变。（入口见FastPriorityQueueNode的UpdatePriority）
  变更后，需要维持大顶堆的大顶，对现有节点（包含新增或者变更节点）根据优先级触发节点上浮CascadeUp或节点下沉CascadeDown。
  采用大顶堆的方式，老样子，采用位运算（<<1）方式计算堆中父节点位置，但只维持了大顶，并没有完全排序，即数组中的元素优先级不是从大到小的。
如果是内部节点动态变更优先级，比如随着节点增加，可能构造这样一棵子树：父节点优先级为8，左右子节点的优先级分别为3和5，它本身就不是完全从大到小，当优先级3的节点优先级变成9，只会让它跟父节点交换，交换后依旧不是完全从大到小。
  此外，新增一个同优先级的节点是不会把原本节点顶后，而是对新增节点进行下沉操作。（见FastPriorityQueueNode的CascadeDown）

private void CascadeUp(T node)
{
    //aka Heapify-up
    int parent;
    if(node.QueueIndex > 1)
    {
        parent = node.QueueIndex >> 1;
        T parentNode = _nodes[parent];
        if(HasHigherOrEqualPriority(parentNode, node))
            return;

        //Node has lower priority value, so move parent down the heap to make room
        _nodes[node.QueueIndex] = parentNode;
        parentNode.QueueIndex = node.QueueIndex;

        node.QueueIndex = parent;
    }
    else
    {
        return;
    }
    while(parent > 1)
    {
        parent >>= 1;
        T parentNode = _nodes[parent];
        if(HasHigherOrEqualPriority(parentNode, node))
            break;

        //Node has lower priority value, so move parent down the heap to make room
        _nodes[node.QueueIndex] = parentNode;
        parentNode.QueueIndex = node.QueueIndex;

        node.QueueIndex = parent;
    }
    _nodes[node.QueueIndex] = node;
}
private void CascadeDown(T node)
{
    //aka Heapify-down
    int finalQueueIndex = node.QueueIndex;
    int childLeftIndex = 2 * finalQueueIndex;

    // If leaf node, we're done
    if(childLeftIndex > _numNodes)
    {
        return;
    }

    // Check if the left-child is higher-priority than the current node
    int childRightIndex = childLeftIndex + 1;
    T childLeft = _nodes[childLeftIndex];
    if(HasHigherPriority(childLeft, node))
    {
        // Check if there is a right child. If not, swap and finish.
        if(childRightIndex > _numNodes)
        {
            node.QueueIndex = childLeftIndex;
            childLeft.QueueIndex = finalQueueIndex;
            _nodes[finalQueueIndex] = childLeft;
            _nodes[childLeftIndex] = node;
            return;
        }
        // Check if the left-child is higher-priority than the right-child
        T childRight = _nodes[childRightIndex];
        if(HasHigherPriority(childLeft, childRight))
        {
            // left is highest, move it up and continue
            childLeft.QueueIndex = finalQueueIndex;
            _nodes[finalQueueIndex] = childLeft;
            finalQueueIndex = childLeftIndex;
        }
        else
        {
            // right is even higher, move it up and continue
            childRight.QueueIndex = finalQueueIndex;
            _nodes[finalQueueIndex] = childRight;
            finalQueueIndex = childRightIndex;
        }
    }
    // Not swapping with left-child, does right-child exist?
    else if(childRightIndex > _numNodes)
    {
        return;
    }
    else
    {
        // Check if the right-child is higher-priority than the current node
        T childRight = _nodes[childRightIndex];
        if(HasHigherPriority(childRight, node))
        {
            childRight.QueueIndex = finalQueueIndex;
            _nodes[finalQueueIndex] = childRight;
            finalQueueIndex = childRightIndex;
        }
        // Neither child is higher-priority than current, so finish and stop.
        else
        {
            return;
        }
    }

    while(true)
    {
        childLeftIndex = 2 * finalQueueIndex;

        // If leaf node, we're done
        if(childLeftIndex > _numNodes)
        {
            node.QueueIndex = finalQueueIndex;
            _nodes[finalQueueIndex] = node;
            break;
        }

        // Check if the left-child is higher-priority than the current node
        childRightIndex = childLeftIndex + 1;
        childLeft = _nodes[childLeftIndex];
        if(HasHigherPriority(childLeft, node))
        {
            // Check if there is a right child. If not, swap and finish.
            if(childRightIndex > _numNodes)
            {
                node.QueueIndex = childLeftIndex;
                childLeft.QueueIndex = finalQueueIndex;
                _nodes[finalQueueIndex] = childLeft;
                _nodes[childLeftIndex] = node;
                break;
            }
            // Check if the left-child is higher-priority than the right-child
            T childRight = _nodes[childRightIndex];
            if(HasHigherPriority(childLeft, childRight))
            {
                // left is highest, move it up and continue
                childLeft.QueueIndex = finalQueueIndex;
                _nodes[finalQueueIndex] = childLeft;
                finalQueueIndex = childLeftIndex;
            }
            else
            {
                // right is even higher, move it up and continue
                childRight.QueueIndex = finalQueueIndex;
                _nodes[finalQueueIndex] = childRight;
                finalQueueIndex = childRightIndex;
            }
        }
        // Not swapping with left-child, does right-child exist?
        else if(childRightIndex > _numNodes)
        {
            node.QueueIndex = finalQueueIndex;
            _nodes[finalQueueIndex] = node;
            break;
        }
        else
        {
            // Check if the right-child is higher-priority than the current node
            T childRight = _nodes[childRightIndex];
            if(HasHigherPriority(childRight, node))
            {
                childRight.QueueIndex = finalQueueIndex;
                _nodes[finalQueueIndex] = childRight;
                finalQueueIndex = childRightIndex;
            }
            // Neither child is higher-priority than current, so finish and stop.
            else
            {
                node.QueueIndex = finalQueueIndex;
                _nodes[finalQueueIndex] = node;
                break;
            }
        }
    }
}

  移除节点如何实现：

  先将移除节点A和末尾节点B做个数组位置上的交换。然后对交换后的B进行大顶堆的调整，并置空尾节点。

  是否支持元素查询

  元素的查询需要自行实现。