[解決済み] Microsoft内部のPriorityQueue<T>のバグ？

質問

.NET FrameworkのPresentationCore.dllにあるジェネリックの PriorityQueue<T> クラスがあり、そのコードは ここで .

並べ替えをテストするために短いプログラムを書きましたが、結果はあまりよくありませんでした。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using MS.Internal;

namespace ConsoleTest {
    public static class ConsoleTest {
        public static void Main() {
            PriorityQueue<int> values = new PriorityQueue<int>(6, Comparer<int>.Default);
            Random random = new Random(88);
            for (int i = 0; i < 6; i++)
                values.Push(random.Next(0, 10000000));
            int lastValue = int.MinValue;
            int temp;
            while (values.Count != 0) {
                temp = values.Top;
                values.Pop();
                if (temp >= lastValue)
                    lastValue = temp;
                else
                    Console.WriteLine("found sorting error");
                Console.WriteLine(temp);
            }
            Console.ReadLine();
        }
    }
}

結果

2789658
3411390
4618917
6996709
found sorting error
6381637
9367782

ソートエラーがあり、サンプルサイズを大きくすると、ソートエラーの数が多少比例して増加します。

何か間違ったことをしたのでしょうか？そうでなければ、どこにバグがあるのでしょうか？ PriorityQueue クラスのコードのバグが正確にどこにあるのか？

どのように解決するには？

この挙動は、初期化ベクトル [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   

そして私たちが行き着く先は... 壊れたヒープです。

正直に言うと、私は作者が何をしようとしていたのか理解できないので、既存のコードを修正することはできません。せいぜい、動作するバージョンと入れ替えることができる程度です (恥ずかしげもなく ウィキペディア ):

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