Lỗi trong PriorityQueue nội bộ của Microsoft <T>?

Question

Trong Khuôn khổ .NET trong PresentationCore.dll, có một lớp PriorityQueue<T> chung có mã có thể được tìm thấy here.

Tôi đã viết một chương trình ngắn để kiểm tra phân loại, và kết quả là không lớn:

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

Kết quả:

2789658 
3411390 
4618917 
6996709 
found sorting error 
6381637 
9367782 

Có một lỗi phân loại, và nếu kích thước mẫu là tăng lên, số lượng lỗi sắp xếp tăng phần nào tương ứng.

Tôi đã làm gì sai? Nếu không, lỗi trong mã của lớp PriorityQueue nằm chính xác ở đâu?

Answer 1

Hành vi có thể được sao chép bằng cách sử dụng vector khởi tạo [0, 1, 2, 4, 5, 3]. Kết quả là:

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

(chúng ta có thể thấy rằng 3 được đặt không chính xác)

Thuật toán Push là đúng. Nó xây dựng một min-heap trong một cách đơn giản:

• Bắt đầu từ phía dưới bên phải
• Nếu giá trị lớn hơn node cha sau đó chèn nó và trở
• Nếu không, đặt thay vì phụ huynh trong vị trí dưới bên phải, sau đó thử chèn giá trị tại nơi cha mẹ (và giữ trao đổi lên cây cho đến đúng nơi đã được tìm thấy)

cây kết quả là:

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

Sự cố xảy ra với phương pháp Pop. Nó bắt đầu bằng cách xem xét nút trên cùng như là một "khoảng trống" để lấp đầy (kể từ khi chúng tôi bật nó):

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

Để điền vào nó, nó tìm kiếm đứa trẻ ngay lập tức thấp nhất (trong trường hợp này: 1). sau đó nó di chuyển giá trị lên đến lấp đầy khoảng trống (và đứa trẻ bây giờ là khoảng cách mới):

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

sau đó nó làm điều chính xác cùng với khoảng cách mới, vì vậy khoảng cách di chuyển xuống một lần nữa:

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

Khi khoảng cách đã chạm đáy, các thuật toán ... có giá trị từ dưới tận cùng bên phải của cây và sử dụng nó để lấp đầy khoảng trống:

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

Bây giờ khoảng cách nằm ở đáy nút ngoài cùng bên phải, nó giảm _count để loại bỏ khoảng cách khỏi cây:

    1 
      / \ 
      / \ 
      4  2 
     /\  
      3 5 

Và chúng tôi kết thúc bằng ... Một đống bị hỏng.

Thành thật mà nói, tôi không hiểu tác giả đang cố gắng làm gì, vì vậy tôi không thể sửa mã hiện có. Tại hầu hết, tôi có thể trao đổi nó với một phiên bản làm việc (không biết xấu hổ sao chép từ 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); 
    } 
} 

Vấn đề chính với mã số đó là việc thực hiện đệ quy, mà sẽ phá vỡ nếu số phần tử quá lớn. Tôi khuyên bạn nên sử dụng thư viện của bên thứ ba được tối ưu hóa thay thế.

---

Chỉnh sửa: Tôi nghĩ tôi đã phát hiện ra những gì còn thiếu. Sau khi lấy nút dưới cùng bên phải, tác giả chỉ quên cân bằng lại đống:

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

Answer 2

Câu trả lời của Kevin Gosse xác định vấn đề. Mặc dù sự cân bằng lại của heap của nó sẽ làm việc, nó không cần thiết nếu bạn sửa chữa vấn đề cơ bản trong vòng loại bỏ ban đầu.

Như ông đã chỉ ra, ý tưởng là thay thế mục ở đầu heap bằng mục thấp nhất, bên phải, và sau đó chọn nó xuống vị trí thích hợp. Đó là một sửa đổi đơn giản của vòng lặp ban đầu:

internal void Pop() 
{ 
    Debug.Assert(_count != 0); 

    if (_count > 0) 
    { 
     --_count; 
     // Logically, we're moving the last item (lowest, right-most) 
     // to the root and then sifting it down. 
     int ix = 0; 
     while (ix < _count/2) 
     { 
      // find the smallest child 
      int smallestChild = HeapLeftChild(ix); 
      int rightChild = HeapRightFromLeft(smallestChild); 
      if (rightChild < _count-1 && _comparer.Compare(_heap[rightChild], _heap[smallestChild]) < 0) 
      { 
       smallestChild = rightChild; 
      } 

      // If the item is less than or equal to the smallest child item, 
      // then we're done. 
      if (_comparer.Compare(_heap[_count], _heap[smallestChild]) <= 0) 
      { 
       break; 
      } 

      // Otherwise, move the child up 
      _heap[ix] = _heap[smallestChild]; 

      // and adjust the index 
      ix = smallestChild; 
     } 
     // Place the item where it belongs 
     _heap[ix] = _heap[_count]; 
     // and clear the position it used to occupy 
     _heap[_count] = default(T); 
    } 
} 

Cũng lưu ý rằng mã được viết bị rò rỉ bộ nhớ. Mã bit này:

 // Fill the last gap by moving the last (i.e., bottom-rightmost) node. 
     _heap[parent] = _heap[_count - 1]; 

Không xóa giá trị từ _heap[_count - 1]. Nếu heap đang lưu trữ các kiểu tham chiếu, thì các tham chiếu vẫn còn trong heap và không thể được thu gom rác cho đến khi bộ nhớ cho đống được thu thập rác. Tôi không biết nơi heap này được sử dụng, nhưng nếu nó lớn và sống cho bất kỳ số lượng đáng kể thời gian, nó có thể gây ra tiêu thụ bộ nhớ dư thừa. Câu trả lời là xóa mục sau khi được sao chép:

_heap[_count - 1] = default(T); 

Mã thay thế của tôi kết hợp sửa chữa đó.