问题描述
在PresentationCore.dll的.NET Framework中，有一个通用的 PriorityQueue< T> 类可以在此处.
In the .NET Framework in PresentationCore.dll, there is a generic PriorityQueue<T> class whose code can be found here.
我写了一个简短的程序来测试排序，结果并不理想:
I wrote a short program to test the sorting, and the results weren't great:
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
存在排序错误，如果样本数量增加，排序错误的数量就会成比例地增加.
There is a sorting error, and if the sample size is increased, the number of sorting errors increases somewhat proportionally.
我做错了什么吗?如果没有， PriorityQueue 类的代码中的错误到底在哪里?
Have I done something wrong? If not, where is the bug in the code of the PriorityQueue class located exactly?
推荐答案
可以使用初始化矢量 [0、1、2、4、5、3] 重现此行为.结果是:
The behavior can be reproduced using the initialization vector [0, 1, 2, 4, 5, 3]. The result is:
(我们可以看到3放置不正确)
(we can see that 3 is incorrectly placed)
Push 算法正确.它以一种直接的方式建立了最小堆:
The Push algorithm is correct. It builds a min-heap in a straightforward way:
- 从右下角开始
- 如果该值大于父节点，则将其插入并返回
- 否则，将父项放到右下角的位置，然后尝试在父项位置插入值(并不断交换树直到找到正确的位置)
生成的树是:
0
/ \
/ \
1 2
/ \ /
4 5 3
问题出在 Pop 方法上.首先将顶部节点视为要填充的间隙"(因为我们将其弹出):
The issue is with the Pop method. It starts by considering the top node as a "gap" to fill (since we popped it):
*
/ \
/ \
1 2
/ \ /
4 5 3
要填充它，它将搜索最低的直接子对象(在这种情况下为1).然后，它将值上移以填补空白(现在孩子是新的空白):
To fill it, it searches for the lowest immediate child (in this case: 1). It then moves the value up to fill the gap (and the child is now the new gap):
1
/ \
/ \
* 2
/ \ /
4 5 3
然后它对新的间隙执行完全相同的操作，因此间隙再次向下移动:
It then does the exact same thing with the new gap, so the gap moves down again:
1
/ \
/ \
4 2
/ \ /
* 5 3
当间隙达到最低点时，算法...将树的最右下角的值用于填充间隙:
When the gap has reached the bottom, the algorithm... takes the bottom-rightmost value of the tree and uses it to fill the gap:
1
/ \
/ \
4 2
/ \ /
3 5 *
现在，该间隙位于最右下角的节点上，它会减小 _count 以便从树中删除该间隙:
Now that the gap is at the bottom-rightmost node, it decrements _count to remove the gap from the tree:
1
/ \
/ \
4 2
/ \
3 5
最后，我们得到了一个破碎的堆.
And we end up with... A broken heap.
老实说，我不了解作者要做什么，所以我无法修复现有代码.最多，我可以将其替换为工作版本(从 Wikipedia 中无耻复制):
To be perfectly honest, I don't understand what the author was trying to do, so I can't fix the existing code. At most, I can swap it with a working version (shamelessly copied from 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);
}
}
该代码的主要问题是递归实现，如果元素数量太大，该实现将中断.我强烈建议您改用经过优化的第三方库.
Main issue with that code is the recursive implementation, which will break if the number of elements is too large. I strongly recommend using an optimized thirdparty library instead.
我想我发现了所缺少的内容.在取得了最右下角的节点之后，作者只是忘记了重新平衡堆:
I think I found out what is missing. After taking the bottom-rightmost node, the author just forgot to rebalance the heap:
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--;
}
这篇关于Microsoft内部的PriorityQueue< T>中的错误?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！