1

私はCで古典的なヒープソートアルゴリズムを実装しています。私はこのコードを何時間も見つめてきましたが、それでも私の人生の何が悪いのか理解できません。入力312 7 4 0 2は適切に機能し、正しいヒープを生成しますが、最後に8を追加すると（サイズを1つ増やします）。ヒープはもう生成されません。何か案は？1つのエラーでばかげていると思います。参考のために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ベースのインデックスを使用しているため、子1、2を持つ要素0があります。要素1と子3、4があります。要素2と子5、6があります。したがって、要素iには子2*i+1とがあり2*i+2ます。

したがって、コードは以下の2つの関数（または）verify_relations()のいずれかに基づいている可能性があります。違いは、ヒープ順序のすべてのエラーを報告しますが、最初の不一致のみを報告することです。どちらの場合も、もちろんヒープが無効であると通知されますが、より詳細なレポートを使用すると、デバッグが容易になる場合があります。コードをテストハーネスで囲みました。主な理由は、ここに投稿する前に、コードが正しいことを合理的に確認したいからです。つまり、分析されているものとエラーが検出されているものを識別するための「タグ」文字列があります。すべてのタグが必要ではないと判断する場合があります。また、関数の代わりにレポートを作成することもできます。verify_relations1()verify_relations2()verify_relations1()verify_relations2()stderrstdout、または検証関数に渡されるファイルストリーム上（実行時に出力を送信する場所を選択できます）。

#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 に答える