c - Heapsort 按降序排列不起作用

Question

我已经看了好几个小时了，还是想不通。如果 heapify 函数中的比较更改为大于，则输出按应有的顺序递增。我希望我的列表按降序排序，但它没有使用以下代码给出正确的输出:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct stuff {
    char *str;
}stuff_t;

void heapify(stuff_t *stuff_array, int i, int n) 
{
    stuff_t temp;
    int left, right, max;

    left = 2*i;
    right = left + 1;
    max = i;
    if (left < n)
        if (strtod(stuff_array[left].str, NULL) < strtod(stuff_array[i].str, NULL))
            max = left;
    if (right < n)
        if (strtod(stuff_array[right].str, NULL) < strtod(stuff_array[max].str, NULL))
            max = right;

    if (max != i)
    {
        temp = stuff_array[i];
        stuff_array[i] = stuff_array[max];
        stuff_array[max] = temp;
        heapify(stuff_array, max, n);
    }
}

void heapsort(stuff_t *stuff_array)
{
    short i,N;
    stuff_t temp; 

    N = 0;
    while (stuff_array[N].str)
        N++;

    for (i = (N/2)-1; i >= 0; i--)
        heapify(stuff_array, i, N);

    for (i = N-1; i >= 1; i--) {
        temp = stuff_array[0];
        stuff_array[0] = stuff_array[i];
        stuff_array[i] = temp;
        heapify(stuff_array, 0, i);
    }
}

int main (int argc, char* argv[])
{
    int i;
    stuff_t *s_list = calloc(4, sizeof(stuff_t));
    stuff_t *s_list1 = calloc(8, sizeof(stuff_t));
    s_list[0].str = "9.3";
    s_list[1].str = "9.3";
    s_list[2].str = "7.8";

    printf("before: ");
    for (i = 0; i < 3; i++)
        printf("%s, ", s_list[i]);
    printf("\n");

    heapsort(s_list);

    printf("after: ");
    for (i = 0; i < 3; i++)
        printf("%s, ", s_list[i]);
    printf("\n");

    s_list1[0].str = "7.5";
    s_list1[1].str = "10.0";
    s_list1[2].str = "10.0";
    s_list1[3].str = "8.3";
    s_list1[4].str = "6.5";
    s_list1[5].str = "5.0";
    s_list1[6].str = "4.6";

    printf("before: ");
    for (i = 0; i < 3; i++)
        printf("%s, ", s_list1[i]);
    printf("\n");

    heapsort(s_list1);

    printf("after: ");
    for (i = 0; i < 7; i++)
        printf("%s, ", s_list1[i]);
    printf("\n");
    return 0;
}

程序输出:

// using less than comparison
before: 9.3, 9.3, 7.8,
after: 9.3, 7.8, 9.3,
before: 7.5, 10.0, 10.0,
after: 10.0, 10.0, 8.3, 7.5, 6.5, 4.6, 5.0,

// using greator than comparison
before: 9.3, 9.3, 7.8,
after: 7.8, 9.3, 9.3,
before: 7.5, 10.0, 10.0,
after: 4.6, 5.0, 6.5, 7.5, 8.3, 10.0, 10.0,

Answer 1

如果从 0 开始计数，则不能使用 i*2 和 i*2+1 作为 child 的地址。问题是 2*0 = 0(左 child 将与 parent 相同)。