私のカスタム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（）メソッドの問題を示しています。あなたは<=

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

とrightための同じを使用する必要がありますminIndexの2人の計算になるよう

あなたlastIndex varが、最後の項目でを指しています。