.net 微软内部 PriorityQueue 中的错误

可以使用初始化向量[0, 1, 2, 4, 5, 3]再现该行为.结果是:

[0，1，2，4，3，5]

(我们可以看到3放错了)

Push算法是正确的.它以一种简单的方式构建最小堆:

• 从右下角开始
• 如果该值大于父 node ，则插入它并返回
• 否则，将父对象放在右下角，然后try 在父对象位置插入值(并继续向上交换树，直到找到正确的位置)

生成的树是:

                 0
               /   \
              /     \
             1       2
           /  \     /
          4    5   3

问题在于Pop方法.首先，将顶部 node 视为要填补的"空白"(因为我们弹出了它):

                 *
               /   \
              /     \
             1       2
           /  \     /
          4    5   3

为了填充它，它搜索最低的直接子对象(在本例中为:1).然后，它向上移动值以填充缺口(现在，子级就是新的缺口):

                 1
               /   \
              /     \
             *       2
           /  \     /
          4    5   3

然后它会对新的间隙做完全相同的事情，所以间隙再次向下移动:

                 1
               /   \
              /     \
             4       2
           /  \     /
          *    5   3

当差距达到底部时，算法...获取树的最右下角的值，并使用它来填补空白:

                 1
               /   \
              /     \
             4       2
           /  \     /
          3    5   *

现在间隙位于最右下角的 node ，它将递减_count以从树中移除间隙:

                 1
               /   \
              /     \
             4       2
           /  \     
          3    5   

我们最终...破堆.

说实话，我不明白作者想做什么，所以我无法修复现有的代码.最多，我可以用一个工作版本(无耻地抄袭Wikipedia)来交换它:

internal void Pop2()
{
    if (_count > 0)
    {
        _count--;
        _heap[0] = _heap[_count];

        Heapify(0);
    }
}

internal void Heapify(int i)
{
    int left = (2 * i) + 1;
    int right = left + 1;
    int smallest = i;

    if (left <= _count && _comparer.Compare(_heap[left], _heap[smallest]) < 0)
    {
        smallest = left;
    }

    if (right <= _count && _comparer.Compare(_heap[right], _heap[smallest]) < 0)
    {
        smallest = right;
    }

    if (smallest != i)
    {
        var pivot = _heap[i];
        _heap[i] = _heap[smallest];
        _heap[smallest] = pivot;

        Heapify(smallest);
    }
}

该代码的主要问题是递归实现，如果元素数量过多，递归实现就会中断.我强烈建议使用优化的第三方库.

编辑:我想我找到了缺失的东西.在获取最右下角的 node 后，作者忘记了重新平衡堆:

internal void Pop()
{
    Debug.Assert(_count != 0);

    if (_count > 1)
    {
        // Loop invariants:
        //
        //  1.  parent is the index of a gap in the logical tree
        //  2.  leftChild is
        //      (a) the index of parent's left child if it has one, or
        //      (b) a value >= _count if parent is a leaf node
        //
        int parent = 0;
        int leftChild = HeapLeftChild(parent);

        while (leftChild < _count)
        {
            int rightChild = HeapRightFromLeft(leftChild);
            int bestChild =
                (rightChild < _count && _comparer.Compare(_heap[rightChild], _heap[leftChild]) < 0) ?
                    rightChild : leftChild;

            // Promote bestChild to fill the gap left by parent.
            _heap[parent] = _heap[bestChild];

            // Restore invariants, i.e., let parent point to the gap.
            parent = bestChild;
            leftChild = HeapLeftChild(parent);
        }

        // Fill the last gap by moving the last (i.e., bottom-rightmost) node.
        _heap[parent] = _heap[_count - 1];

        // FIX: Rebalance the heap
        int index = parent;
        var value = _heap[parent];

        while (index > 0)
        {
            int parentIndex = HeapParent(index);
            if (_comparer.Compare(value, _heap[parentIndex]) < 0)
            {
                // value is a better match than the parent node so exchange
                // places to preserve the "heap" property.
                var pivot = _heap[index];
                _heap[index] = _heap[parentIndex];
                _heap[parentIndex] = pivot;
                index = parentIndex;
            }
            else
            {
                // Heap is balanced
                break;
            }
        }
    }

    _count--;
}