微软内部的PriorityQueue <T>存在问题？
在PresentationCore.dll的.NET Framework中，有一个通用的PriorityQueue<T>类，其代码可以在这里find。
我写了一个简短的程序来testingsorting，结果并不是很好：
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
有一个sorting错误，如果样本大小增加，sorting错误的数量成比例地增加。
我做错了什么？ 如果不是，那么PriorityQueue类的代码中的错误在哪里呢？
行为可以使用初始化向量[0, 1, 2, 4, 5, 3] 0,1,2,4,5,3]来重现。 结果是：
[0，1，2，4，3，5]
（我们可以看到3被错误地放置）
Pushalgorithm是正确的。 它以直截了当的方式build立了一个小堆：
- 从右下angular开始
- 如果该值大于父节点，则插入并返回
- 否则，把父母放在右下angular的位置，然后尝试在父母的地方插入值（并保持换树，直到find正确的位置）
生成的树是：
0 / \ / \ 1 2 / \ / 4 5 3
问题是用Pop方法。 它首先考虑顶部节点作为填补的“空白”（因为我们popup它）：
* / \ / \ 1 2 / \ / 4 5 3
为了填补它，它search最低的直接孩子（在这种情况下：1）。 然后，它将价值向上移动以弥补差距（现在孩子已经是新的差距了）：
1 / \ / \ * 2 / \ / 4 5 3
然后在新的差距上做同样的事情，所以差距再次下降：
1 / \ / \ 4 2 / \ / * 5 3
当差距达到底部时，algorithm…取树的右下angular值并用它填补空白：
1 / \ / \ 4 2 / \ / 3 5 *
现在差距位于最右下angular的节点上，它会减less_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); } }
该代码的主要问题是recursion实现，如果元素数量太大，将会中断实现。 我强烈build议使用优化的第三方库。
编辑：我想我发现了什么是缺less的。 在采取最右下angular的节点之后，作者忘记重新平衡堆：
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, ie, let parent point to the gap. parent = bestChild; leftChild = HeapLeftChild(parent); } // Fill the last gap by moving the last (ie, 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--; }
Kevin Gosse的答案确定了问题。 尽pipe他对堆的重新平衡会起作用，但是如果你在最初的移除循环中解决了基本的问题，那就没有必要了。
正如他指出的，这个想法是用最低的，最右边的物品replace堆顶部的物品，然后筛选到合适的位置。 这是对原始循环的简单修改：
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); } }
还要注意，写入的代码有内存泄漏。 这一点代码：
// Fill the last gap by moving the last (ie, bottom-rightmost) node. _heap[parent] = _heap[_count - 1];
不清除_heap[_count - 1] 。 如果堆存储引用types，则引用保留在堆中，并且不能垃圾收集，直到堆的内存被垃圾收集为止。 我不知道这个堆是用在哪里的，但是如果它很大并且在很长一段时间内生存，可能会导致内存消耗过多。 答案是复制后的项目清除：
_heap[_count - 1] = default(T);
我的replace代码合并了该修复程序。
