c - Heapsort 对任何类型的元素都不起作用

Question

任务是为数组中未知类型的元素编写堆排序(仅使用 C 代码)，但我的代码不起作用。对于以下数字输出是 '-100 7 -4 0 33 -3 67 1 5 44' 我也尝试将相同的代码仅用于 int 输入并且它工作得很好。所以我认为问题在于将其更改为任何类型的输入。

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <memory.h>
typedef int typeEl;
int compare(const void* a, const void* b)
{

    return (*(typeEl*)a - *(typeEl*)b);
}
void swap(void* a, void* b, size_t sizeOfElem) {
    void* tmp = calloc(1,sizeOfElem);
    memcpy(tmp, a, sizeOfElem);
    memcpy(a, b, sizeOfElem);
    memcpy(b, tmp, sizeOfElem);
} 
void heapify (int pos, int n, void* arr, size_t sizeOfElem, int (*comp)(const void* c, const void* d)) { 
    while (2 * pos + 1 < n) {

        int t = 2 * pos +1;
        if (2 * pos + 2 < n && ((char *)arr + (2*pos+2)*sizeOfElem) >= ((char *)arr + t*sizeOfElem))
        {
            t = 2 * pos + 2;
        }
        if (comp((void *) ((char *)arr + pos*sizeOfElem), ((char *)arr + t*sizeOfElem))<0) {
            swap((void *) ((char *)arr + pos*sizeOfElem), (void *) ((char *)arr + t*sizeOfElem), sizeOfElem);
            pos = t;
        } 
        else break;

    }
}

void heap_make(int n, void* arr, size_t sizeOfElem)
{
    for (int i = n - 1; i >= 0; i--)
    {
        heapify(i, n, arr, sizeOfElem, compare );
    }
}

void heap_sort(int n, void* arr, size_t sizeOfElem)
{
    heap_make(n, arr, sizeOfElem);
    while(n>0)
    {
        swap((void *) ((char *)arr), (void *) ((char *)arr + (n-1)*sizeOfElem), sizeOfElem);;
        n--;
        heapify(0,n, arr, sizeOfElem, compare);
    }
}


 int main() {
   int n;
   int m[10] = {1,-3,5,-100,7,33,44,67,-4, 0};

   heap_sort(10, m, sizeof(int));

   for (n=0; n<10; n++)
        printf ("%d ",m[n]);

   return 0;
}

谁能给个建议？感谢您的帮助!

Answer 1

解码别人的代码可能非常困难 - 特别是当您进行各种复杂的索引等操作时。我有一个 heapify 的旧副本(来自早期的答案 - https://stackoverflow.com/a/19749300/1967396)，我修改了它适用于任何类型 - 并包括完整的排序。

这并没有完全回答“为什么您的代码不起作用”这个问题 - 但它确实向您展示了一些您在尝试回答该问题时可能想要实现的简单技术。通常，代码的可读性越高，调试就越容易。

请注意，为了提高可读性，我引入了几个额外的变量(和额外的代码行)- childLeft 和 childRight 绝对有用；此外，一旦为元素的指针建立了数据类型，就可以对元素进行索引 - 因为代码开头有 typedef，所以我通过以下方式简化了一些事情

typeEl *array;

之后我可以用

索引数组

array[pos];

这比

更具可读性(因此更不容易出错)

*((void *) ((char *)arr + pos*sizeOfElem))

我还根据数组和需要交换的两个元素的索引定义了 swap:

void swap(typeEl *arr, int i, int j)

这再次使代码更具可读性(另请注意，我不必执行 calloc)。

无论如何 - 这是代码:

#include <stdio.h>

// define the type of the array that will be sorted:
typedef double typeEl;

void buildHeap(typeEl array[], int n);
void heapify(typeEl array[], int n,  int i);
void heapsort(typeEl array[], int n);
void swap(typeEl array[], int indexA, int indexB);
void printTree(void);

int compare(typeEl a, typeEl b);

typeEl* TREE; // global variable used for printing the entire tree

int main(int argc, char *argv[])
{
typeEl heapArray[] = {1,-3,5,-100,7,33,44,67,-4, 0};
//{0, 1, 2, 3, 4, 5, 6 , 7, 8 ,9 ,10 , 11, 12, 13 ,14 ,15};
int n = sizeof(heapArray)/sizeof(typeEl);
TREE = heapArray;

printf("initial tree:\n");
printTree();
heapsort(heapArray, n);
printf("after heapify\n");
printTree();
printf("as a sorted array:\n");
for(int ii = 0; ii < n; ii++) printf("%d ", (int)heapArray[ii]);
printf("\n");
return 0;
}

void printTree(void)
{
// lazy way to print the entire tree...
  typeEl* array = TREE;
  printf("                        %3d\n ", (int)array[0]);
  printf("            %3d                     %3d\n", (int)array[1], (int)array[2]);
  printf("      %3d         %3d         %3d         %3d\n", (int)array[3], (int)(int)array[4], (int)array[5], (int)array[6]);
  printf("   %3d   %3d   %3d\n", (int)array[7], (int)array[8], (int)array[9]);

  printf("\n");
}

void heapsort(typeEl array[], int n) {
  int i;
  buildHeap(array, n);
  for(i = 1; i < n; i++) {
    buildHeap(array + i, n - i);
  }
}

void buildHeap(typeEl array[], int n)
{
  // change starting condition
  int i = n/2;
  while(i > 0) heapify(array, n,--i);
}

void heapify(typeEl array[], int n,  int i)
{
  // mark nodes initially as -1 to distinguish from "valid" zero
  int childLeft = -1, childRight = -1;
  int largest = i;

  // see if we have valid child nodes:
  if( 2 * i + 1 < n ) childLeft  = 2 * i + 1;
  if( 2 * i + 2 < n ) childRight = 2 * i + 2;

  // see if any nodes are invalid now:
  if(childLeft  < 0 && childRight < 0) return;
  if(childLeft  < 0) childLeft  = childRight;  // can't happen, ever.
  if(childRight < 0) childRight = childLeft; 

  // printf("child left [%i] = %i  child right [%i] = %i\n", childLeft, array[childLeft], childRight, array[childRight]);
  if (compare(array[childLeft], array[i] )) largest = childLeft;
  if (compare(array[childRight] , array[largest])) largest = childRight;
  if(largest != i)
  {
    swap(array, i,largest);
    heapify(array, n, largest);
  }
}

void swap(typeEl array[], int indexA, int indexB)
{
  // printf("swap [%i] %i with [%i] %i\n", indexA, array[indexA], indexB, array[indexB]);
  typeEl temp = array[indexA];
  array[indexA] = array[indexB];
  array[indexB] = temp;
}

int compare(typeEl a, typeEl b) {
  return (a - b>0)?1:0;
}

示例输出:

initial tree:
                          1
              -3                       5
      -100           7          33          44
    67    -4     0

after heapify
                         67
              44                      33
        7           5           1           0
    -3    -4   -100

as a sorted array:
67 44 33 7 5 1 0 -3 -4 -100

如您所见，它是从高到低排序的。显然，您可以通过简单地更改 compare 函数来更改它。