執行堆排序時遇到問題C排序C

Question

我在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]); 
    } 
} 

Answer 1

線

heapify(&n, largest, size); 

應該

heapify(f, largest, size); 
     ^

Answer 2

除了這alestanis確定，你應該看看，讓您的verify_relations()代碼更徹底，因爲它的主要缺陷不驗證整個堆。

在堆，其中陣列索引基於1（從0開始在C代替），然後爲每個元件a[i]，如果相應的元件a[i*2]存在，那麼a[i] <= a[i*2];如果相應的元素a[i*2+1]存在，那麼a[i] <= a[i*2+1]。

由於我們使用基於0的索引在C中工作，因此您的元素爲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); 
}