我正在尝试使用最小堆实现堆排序。输入是正整数数组,数组的零索引存储大小。谁能发现我的错误?这里使用的语言是 C#。该算法有时可以正常工作,但对于更大的数组,根不是数组中的最小值。
static void CreateMinHeap(int[] input)
{
input[0] = input.Length - 1;
for (int i = (input[0] / 2); i > 0; i--)
{
MinHeapify(input, i);
}
}
static void MinHeapify(int[] input, int index)
{
var left = 2 * index;
var right = 2 * index + 1;
int smallest;
if (left < input.Length && input[left] < input[index])
smallest = left;
else
smallest = index;
if (right < input.Length && input[right] < input[smallest])
smallest = right;
if (smallest != index)
{
Swap(ref input[smallest], ref input[index]);
MinHeapify(input, smallest);
}
}
static public void HeapSort(int[] input)
{
CreateMinHeap(input);
for (int i = input[0]; i > 0; i--)
{
Swap(ref input[1], ref input[i]);
input[0]--;
MinHeapify(input, 1);
}
}
static public void Swap(ref int a, ref int b)
{
var temp = a;
a = b;
b = temp;
}
最佳答案
背景
据我了解,您在两个分区中使用数组。
第一个分区包含堆,第二个分区(开始为空)包含排序后的值。
在 HeapSort 期间,第一个分区的大小减小,第二个分区的大小增加,直到您有一个排序数组。
错误
问题是,当您运行 MinHeapify 时,您没有告诉它堆的长度已经减少,所以它正在尝试堆化您的一些已排序节点。
修复
您正在跟踪条目 input[0] 中的堆大小,因此这应该很容易修复。
尝试改变:
if (left < input.Length && input[left] < input[index])
smallest = left;
else
smallest = index;
if (right < input.Length && input[right] < input[smallest])
smallest = right;
到
if (left <= input[0] && input[left] < input[index])
smallest = left;
else
smallest = index;
if (right <= input[0] && input[right] < input[smallest])
smallest = right;
关于c# - 具有最小堆的 Heapsort 无法正常工作,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21612077/