1

我正在用 C 语言实现经典的堆排序算法。我已经盯着这段代码看了好几个小时，但仍然无法弄清楚我这辈子出了什么问题。输入 3 1 2 7 4 0 2 运行良好并产生正确的堆，但是当我在末尾添加 8 时（并将大小增加一）。它不再产生堆。有任何想法吗？我认为这只是一个错误的愚蠢行为。供参考http://en.wikipedia.org/wiki/Heapsort

#include <ctype.h>
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <errno.h>
#include <math.h>
#include <string.h>

#define MAX_ARR 1024

void build_heap(int * fn, int len);
void heapify(int *f, int n, int size);
void verify_relations(int *f, int n);
void print_nums (int n[], int len);
void swap(int * a, int * b);
void heap_sort(int * a, int len);

int main(int argc, char **argv){
    /* input works -- 3 1 2 7 4 0 2 */
    /* input broken -- 3 1 2 7 4 0 2 8 */
    int nums[100] = { 3, 1, 2, 7, 4, 0, 2, 8 };

    int len = 8;

    build_heap(nums, len);
    verify_relations(nums, len);
    print_nums(nums, len);
    return 0;
}


void heap_sort(int nums[], int len){
    int i;
    build_heap(nums, len);
    for (i = len; i > 0; --i)
    {
        swap(&nums[1], &nums[i]);
        heapify(nums, 1, len);
    }

}

void build_heap(int * nums, int len) {
    int size = len, i;
    for (i = size; i >= 0; i--){
        heapify(nums, i, size);
    }
}

void heapify(int f[], int n, int size){

    int left = 2 * n,
    right = 2 * n + 1,
    largest = 0;

    if (left < size && f[left] >= f[n])
        largest = left;
    else
        largest = n;

    if (right < size && f[right] >= f[largest])
        largest = right;

    if (largest != n) {
        swap(&f[n], &f[largest]);
        heapify(&n, largest, size);
    }
}

void swap(int * a, int * b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

void verify_relations(int a[], int n){

    if (a[0] >= a[1] && a[0] >= a[2])
        printf("True - '%d >= %d && %d >= %d' \n", a[0], a[1], a[0], a[2]);
    else
        printf("False\n");

    if (a[1] >= a[3] && a[1] >= a[4])
        printf("True - '%d >= %d && %d >= %d' \n", a[1], a[3], a[1], a[4]);
    else
        printf("False\n");

    if (a[2] >= a[4] && a[2] >= a[5])
        printf("True - '%d >= %d && %d >= %d' \n", a[2], a[4], a[3], a[5]);
    else
        printf("False\n");
}


void print_nums (int n[], int len) {
    int c;
    for (c = 0; c < len; c++){
        printf("%d ", n[c]);
    }
}
4

2 回答 2

7

线

heapify(&n, largest, size);

应该

heapify(f, largest, size);
        ^
于 2012-10-28T14:44:31.257 回答
1

除了alestanis确定的主要错误之外，您应该考虑使您的verify_relations()代码更彻底，因为它不会验证整个堆。

在数组索引从 1 开始（而不是 C 中从 0 开始）的堆中，对于每个元素a[i]，如果存在相应元素a[i*2]，则a[i] <= a[i*2]; 如果对应的元素a[i*2+1]存在，则a[i] <= a[i*2+1].

由于我们在 C 中使用基于 0 的索引，因此您有元素 0 和子元素 1、2；您有元素 1 和孩子 3、4；你有元素 2 和孩子 5、6；所以元素i有孩子2*i+1和2*i+2。

因此，您的verify_relations()代码可能基于以下两个函数之一（verify_relations1()或verify_relations2()）。不同之处在于verify_relations1()报告堆排序中的每个错误，但verify_relations2()只报告第一个不匹配。当然，在这两种情况下，您都会被告知堆无效，但有时更全面的报告可能会使调试更容易。我已将代码包含在测试工具中，主要是因为我喜欢在将代码发布到此处之前合理地确定代码是正确的。这意味着我有“标签”字符串来识别正在分析的内容以及发现的错误。您可能会决定不需要所有标签。您可能还决定让函数报告stderr而不是stdout，或在传递给验证函数的文件流上（因此您可以选择在运行时输出的位置）。

#include <assert.h>
#include <stdio.h>

enum { HEAP_OK, HEAP_FAIL };

static int cmp_heap_elements(const int *heap, int node1, int node2, const char *tag)
{
     int rc = HEAP_OK;
     if (heap[node1] > heap[node2])
     {
         rc = HEAP_FAIL;
         printf("%s: heap relation does not hold between heap[%d] = %d and heap[%d] = %d\n",
                 tag, node1, heap[node1], node2, heap[node2]);
     }
     return rc;
}

/* Report on every violation */
static int verify_relations1(const int *heap, int size)
{
     int rc = HEAP_OK;
     for (int i = 0; i < size / 2; i++)
     {
         assert(2*i+1 < size);
         if (2*i+1 >= size)
             break;
         int rv = cmp_heap_elements(heap, i, i*2+1, "R1");
         if (rc == HEAP_OK)
             rc = rv;
         if (2*i+2 >= size)
             break;
         rv = cmp_heap_elements(heap, i, i*2+2, "R1");
         if (rc == HEAP_OK)
             rc = rv;
     }
     return(rc);
}

/* Report on first violation - leaving others undiagnosed */
static int verify_relations2(const int *heap, int size)
{
     for (int i = 0; i < size / 2; i++)
     {
         assert(2*i+1 < size);
         if (2*i+1 >= size)
             break;          // Or: return(HEAP_OK);
         if (cmp_heap_elements(heap, i, i*2+1, "R2") != HEAP_OK)
             return(HEAP_FAIL);
         if (2*i+2 >= size)
             break;          // Or: return(HEAP_OK);
         if (cmp_heap_elements(heap, i, i*2+1, "R2") != HEAP_OK)
             return(HEAP_FAIL);
     }
     return(HEAP_OK);
}

static void print_heap(const int *heap, int size, const char *tag)
{
    printf("%s:", tag);
    for (int i = 0; i < size; i++)
        printf(" %d", heap[i]);
    putchar('\n');
}

static void check_heap(int *heap, int size, const char *tag)
{
    print_heap(heap, size, tag);
    if (verify_relations1(heap, size) != HEAP_OK)
        printf("%s %d - FAIL\n", tag, size);
    if (verify_relations2(heap, size) != HEAP_OK)
        printf("%s %d - FAIL\n", tag, size);
}

int main(void)
{
    int heap1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int heap2[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    int heap3[] = { 1, 2, 6, 4, 10, 3, 7, 8, 9, 5 };
    const int heap1_sz = sizeof(heap1) / sizeof(heap1[0]);
    const int heap2_sz = sizeof(heap2) / sizeof(heap2[0]);
    const int heap3_sz = sizeof(heap3) / sizeof(heap3[0]);
    assert(heap1_sz == heap2_sz && heap1_sz == heap3_sz);

    for (int size = 1; size <= heap1_sz; size++)
    {
        check_heap(heap1, size, "heap1");
        check_heap(heap2, size, "heap2");
        check_heap(heap3, size, "heap3");
    }
    return(0);
}
于 2012-10-28T16:59:05.413 回答