C 中的 Heapsort 实现 - 数组错误

Question

我试图在 C 中实现 Heapsort 算法，但我不确定我是否做对了。我也有一个错误 "variably modified 'A' at file scope"。我在 Whosebug 上搜索类似的主题，我发现 heapSize 应该是 const 但后来我不能将它用作我的函数中的变量。我该怎么办？

#include <stdio.h>
#include <math.h>

int heapSize = 100;
int length;
int A[heapSize];

int Heapify(int i) {
  int l = 2*i;
  int r = 2*i + 1;
  int largest;
  int tmp;

  if( l <= heapSize && A[l] > A[i]) largest = l;
  else largest = i;

  if (r <= heapSize && A[r] > A[largest]) largest = r;

  if (largest != i) {
    tmp = A[i];
    A[i] = A[largest];
    A[largest] = tmp;
    }
}

int BuildHeap() {
  heapSize = length;
  int i;

  for (i = floor(length/2); i <= 1; i--) {
    Heapify(i);
    }
}

int main(void) {
  int i,tmp;

  BuildHeap();

  for (i = length; i <= 2; i--) {
    tmp = A[heapSize];
    A[heapSize] = A[1];
    A[1] = A[heapSize];

    heapSize = heapSize - 1;

    Heapify(1);
    }
}

编辑：我将程序的第一部分更改为：

#include <stdio.h>
#define LENGTH 100


int heapSize = 10;
int A[LENGTH]

并根据您的建议，将 "floor(length/2)" 替换为 "LENGTH/2"。我通过编译解决了我的问题，但我很确定这个实现很糟糕。好吧，无论如何，非常感谢你的帮助。非常感谢。

Answer 1

你的代码有很多问题。

首先，您声明了一个全局 int length 变量，但从未为其赋值。所以 length 总是零。

在 BuildHeap() 你做：

    for (i = floor(length/2); i <= 1; i--) ...

以 floor(0/2) 开头，即 i==0。该值小于 1，因此循环进行第一次迭代，并使用 i-- 表达式递减 i — 并且 i 变为减一。然后循环继续进行，直到 i 值回绕零变为正值（并且大于 1）。对于 32 位整数，大约需要 21.4 亿次迭代...

您的 main() 做的第一件事是调用 BuildHeap()，后者又调用（多次）Heapify()。后者比较数组项来决定是否应该交换它们——但它们没有被分配任何值！您永远不会用任何数据填充 A 数组...

您是否注意到您比较和交换数组之外的项目（实际上，在数组之前） , 因为 BuildHeap() 将 i 递减到零以下并将负索引值传递给 Heapify()...?

您的 Heapify 例程最多在数组中执行一次交换。似乎还不够。假设堆已经有 3 层深，当前项出现在堆中最小的一个；它应该深入到最深层次，但你如何做到这一点？单次交换将项目向下移动一个级别。

这就是你可以做到的。

首先，确定要处理的数据的最大大小并准备数组：

#define LENGTH 100

int A[LENGTH + 1];

（你需要 'plus one' 因为 A[0] 不会成为堆的一部分——为什么？）

然后准备变量来存储实际大小的数据：

int dataSize;
int heapSize;

和一个填充数组的例程。您可以读取用户输入或从文件加载数据，或仅通过某种算法填充数组。

void FillArrayAscending() {
    dataSize = 16;
    for(int i = 1; i <= dataSize; i ++)
        A[i] = i;
}
void FillArrayDescending() {
    dataSize = 25;
    for(int i = 1; i <= dataSize; i ++)
        A[i] = 50 - i;
}
void FillArrayCrossed() {
    dataSize = 20;
    for(int i = 1; i <= dataSize; i += 2)
        A[i] = 10 + i;
    for(int i = 2; i <= dataSize; i += 2)
        A[i] = 30 - i;
}

那么你可以'heapify'。为此，您将项目从堆中筛选出来 – 您迭代交换直到项目到达其位置：

void SiftDown(int i) {
    while(i < heapSize) {
        int largest = i;

        if(2*i <= heapSize && A[i] < A[2*i])
            largest = 2*i;
        if(2*i + 1 <= heapSize && A[largest] < A[2*i + 1])
            largest = 2*i + 1;

        if(largest == i)
            break;  // the item reached its place

        A[0] = A[largest];
        A[largest] = A[i];
        A[i] = A[0];
        i = largest;  // new position to sift down...
    }
}

i 表示要筛选的项目，largest 表示交换目的地，A[0] 可以用作临时存储（为什么？）。

现在可以在数组中建堆了：

void BuildHeap() {
    heapSize = dataSize;
    for(int i = heapSize/2; i >= 1; i --)
        SiftDown(i);
}

并按降序从堆中检索项目：

void ExtractHeap() {
    while(heapSize > 1) {
        A[0] = A[1];        // take the max item from a heap
        A[1] = A[heapSize]; // replace it with the last one
        A[heapSize] = A[0]; // add the max one to the sorted part
        heapSize --;
        SiftDown(1);        // re-heapify
    }
}

现在你可以进行整个处理了：

int main(int, char**)
{
    FillArrayAscending();  // or Descending or...
    BuildHeap();
    ExtractHeap();

    // and here you can print the array contents
    // for indices 1 .. dataSize
    // to verify it is actually sorted
}

C 中的 Heapsort 实现 - 数组错误

Heapsort implementation in C - array error

c

sorting

heapsort