我的自定义 BinaryHeap 的顺序并不总是正确的

Question

我创建了一个 BinaryHeap 类。

public class BinaryHeap<T>
{
    private List<T> _heap;

    // Constructor
    public BinaryHeap(int capacity, IComparer<T> comparer)
    {
        this._heap = new List<T>(capacity);
        Comparer = comparer ?? Comparer<T>.Default;
    }

    // Constructor
    public BinaryHeap(int capacity) : this(capacity, (IComparer<T>)null) { }

    // Gets/sets IComparer
    public IComparer<T> Comparer { get; private set; }

    // Gets/sets the capacity
    public int Capacity
    {
        get { return this._heap.Capacity; }
        set { this._heap.Capacity = value; }
    }

    // Gets the number of elements
    public int Count
    {
        get { return this._heap.Count; }
    }

    // Inserts the specified element within this BinaryHeap.
    public void Insert(T element)
    {
        // Add the element as the last element.
        this._heap.Add(element);

        // Index of last added element.
        int last = this._heap.Count - 1;

        int parent;
        T swap;
        while (last > 0)
        {
            parent = (last - 1) >> 1;   // parent(i) = (i-1)/2

            if (Comparer.Compare(this._heap[parent], this._heap[last]) <= 0)
                break;   // exit while if the current node is lesser than its parent.

            swap = this._heap[last];                // If the parent is greater
            this._heap[last] = this._heap[parent];  // than the current node,
            this._heap[parent] = swap;              // then swap them.

            last = parent;   // Updates index of last added element.
        }
    }

    /// <summary>
    /// 
    /// </summary>
    /// <returns></returns>
    public T Remove()
    {
        if (this._heap.Count > 0)
        {
            // Save the element.
            T result = this._heap[0];

            int lastIndex = this._heap.Count - 1;   // The last element moves
            this._heap[0] = this._heap[lastIndex];  // moves to the root
            this._heap.RemoveAt(lastIndex);         // of this tree.
            lastIndex--;   // Update position of last element.

            int i = 0;   // Position of moved node.
            while (i < lastIndex)
            {
                int minIndex = i;

                int left = (i << 1) + 1;   // left(i) = (i*2)+1
                if (left < lastIndex && Comparer.Compare(this._heap[left], this._heap[minIndex]) < 0)
                {
                    minIndex = left;
                }

                int right = left + 1;   // right(i) = (i*2)+2
                if (right < lastIndex && Comparer.Compare(this._heap[right], this._heap[minIndex]) < 0)
                {
                    minIndex = right;
                }

                if (minIndex != i)
                {
                    // If one of the two children is lesser than the parent,
                    // then swap the latter with the lesser child.
                    T temp = this._heap[i];
                    this._heap[i] = this._heap[minIndex];
                    this._heap[minIndex] = temp;
                    i = minIndex;
                }
                else break;
            }

            // Return the minimum element that has been removed.
            return result;
        }
        else throw new InvalidOperationException("BinaryHeap is empty.");
    }
}

在执行一些测试时，例如以下测试作为简单队列。

BinaryHeap<int> q = new BinaryHeap<int>(0);
int count = 50;
for (int i = 0; i < count; i++)
    q.Insert(i);
for (int i = 0; i < count; i++)
    Console.WriteLine(q.Remove());
Console.ReadLine();

返回的元素应该按升序排列，但倒数第三个元素和倒数第二个元素几乎总是顺序错误。例如，对于 count = 50，输出为：

// previous element are in correct order
44
45
46
48   // wrong order
47   // wrong order
49

测试多个 count 值，此问题并不总是发生。 为什么？ 我该如何解决这个问题？

Answer 1

该症状表明Remove() 方法中存在问题。

您的 lastIndex 变量指向最后一项，因此在 minIndex 的 2 次计算中，您应该使用 <=

 // if (left < lastIndex && ...)
    if (left <= lastIndex && ...)

，对于 也是如此>对。