[c#] Microsoft의 내부 PriorityQueue <T>에 버그가 있습니까?

이 동작은 초기화 벡터를 사용하여 재현 할 수 있습니다 [0, 1, 2, 4, 5, 3]. 결과는 다음과 같습니다.

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

(3이 잘못 배치 된 것을 볼 수 있습니다)

Push알고리즘은 올바른 것입니다. 간단한 방법으로 최소 힙을 빌드합니다.

• 오른쪽 하단에서 시작
• 값이 부모 노드보다 크면 삽입하고 반환
• 그렇지 않으면 부모를 오른쪽 아래 위치에 놓고 부모 위치에 값을 삽입 해보십시오 (올바른 위치를 찾을 때까지 트리를 계속 바꾸십시오).

결과 트리는 다음과 같습니다.

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

문제는 Pop방법에 있습니다. 맨 위 노드를 채울 “간격”으로 간주하는 것으로 시작합니다 (팝업 이후).

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

이를 채우기 위해 가장 낮은 직계 자식을 검색합니다 (이 경우 : 1). 그런 다음 값을 위로 이동하여 간격을 채 웁니다 (이제 자식이 새 간격이 됨).

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

그런 다음 새 간격과 똑같은 작업을 수행하므로 간격이 다시 아래로 이동합니다.

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

간격이 맨 아래에 도달하면 알고리즘은 … 트리의 맨 오른쪽 아래 값을 가져와 간격을 채우는 데 사용합니다.

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

이제 간격이 맨 오른쪽 아래 노드에 _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);
    }
}

이 코드의 주요 문제는 재귀 구현으로, 요소 수가 너무 많으면 중단됩니다. 대신 최적화 된 타사 라이브러리를 사용하는 것이 좋습니다.

---

편집 : 나는 무엇이 빠졌는지 알아 냈다고 생각합니다. 맨 오른쪽 아래 노드를 가져온 후 작성자는 힙의 균형을 다시 조정하는 것을 잊었습니다.

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--;
}