我的自定義BinaryHeap的順序並不總是正確的

Question

我創建了一個BinaryHeap<T>類。

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 VAR在最後一個項目指向，所以在2個計算minIndex的，你應該使用<=

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

與同爲right。