c# - 具有最小堆的 Heapsort 无法正常工作

Question

我正在尝试使用最小堆实现堆排序。输入是正整数数组，数组的零索引存储大小。谁能发现我的错误？这里使用的语言是 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;
    }

Answer 1

背景

据我了解，您在两个分区中使用数组。

第一个分区包含堆，第二个分区(开始为空)包含排序后的值。

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