C Реализация пирамидальной сортировки не изменяет массив

Я реализовал пирамидальную сортировку в качестве упражнения с заданными API-интерфейсами двоичной кучи и отлично справился. Затем я попытался реализовать его с нуля и потерпел неудачу. Алгоритм должен, учитывая массив размера n, превратить его в двоичную кучу на месте и со сложностью O (logN); затем перейдите к извлечению корня (max elem), поместите его в конец массива и сбросьте свойства кучи. Во всяком случае, это просто не работает, я не могу понять, почему. Вот код:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
//----------------------------------------------------------------------------------------
#define DEBUG_MODE 1
#define parent_index(i) (((i + 1) % 2)? ((i >>1)-1):(((i+1)>>1)-1) )
#define left_child_index(i) (((i + 1) << 1)-1)
#define right_child_index(i) (((i + 1) << 1))

#define is_higher(a, b) (((a) > (b))? (a) : (b))

#define HEAP_SORT_TEST_ARRAY_SIZE 10
#define HEAP_SORT_TEST_TEST_TIMES 8
#define is_odd(u) (u - ((u >> 1) << 1))

typedef int b_heap_entry;
typedef struct heap
{
    b_heap_entry* array;
    int capacity;
    int size;
} b_heap;
//----------------------------------------------------------------------------------------
void array_print(int* array, unsigned size)
{
    unsigned u;
    printf("[");
    for(u = 0; u < size; u++)
        printf("%d, ", array[u]);
    printf("\b\b]\n");
}
#if DEBUG_MODE
                                                                                                        void heap_print(b_heap* h)
                                                                                                        {
                                                                                                            printf("BINARY HEAP:\n(size %d)\n", h->size);
                                                                                                            unsigned u;
                                                                                                            for(u = 0; u <= h->size; u++)
                                                                                                            {
                                                                                                                if(is_power2(u+1)) printf("\n");
                                                                                                                printf("<%d>    ", h->array[u]);
                                                                                                            }
                                                                                                            printf("\n");
                                                                                                        }
#endif
//----------------------------------------------------------------------------------------
int closest_lower_p2(int i)
{
    int n;
    for(n = 0; i >1; i = i >> 1)
        n++;
    return (1 << n);
}
#if DEBUG_MODE
                                                                                                        int is_power2(unsigned u)
                                                                                                        {
                                                                                                            if(u == 1)
                                                                                                                return 0;
                                                                                                            for(; u > 1; u = u >> 1)
                                                                                                                if(is_odd(u)) return 0;
                                                                                                            return 1;
                                                                                                        }
#endif
//----------------------------------------------------------------------------------------
inline void siftDown(b_heap* h, int i)
{
    int child_index;
    b_heap_entry tmp;
    while(left_child_index(i) <= h->size)
    {
        /*
         * child index is the index of the greater child
         */
        child_index = ((right_child_index(i) >= h->size)||
        (is_higher(h->array[left_child_index(i)], h->array[right_child_index(i)])))?
         left_child_index(i) : right_child_index(i);
        /*
         * if the node at index i is lesser than 1 of its children, we swap them, let i be the new 
         * parent index (child_index) and keep going until i is greater than both its children or 
         * there are no more children (i is now a leaf)
         */
        if(is_higher(h->array[i], h->array[child_index]))
            return;
        tmp = h->array[i];
        h->array[i] = h->array[child_index];
        h->array[child_index] = tmp;
        i = child_index;
    }
}
//----------------------------------------------------------------------------------------
b_heap_entry heap_poll(b_heap* h) {
/*
 * First we find the last leaf and swap the root with it
 * (Since we can remove leaves without having to modify the
 * shape of the heap)
 */
    b_heap_entry root = h->array[0];
    h->array[0] = h->array[--(h->size)];
/*
 * Now we restore the order
 */
    siftDown(h, 0);
    return root;
}
//----------------------------------------------------------------------------------------
b_heap* array2heap(int * array, int size) 
{
#if DEBUG_MODE
                                                                                                            printf("Making the array\n");
                                                                                                            array_print(array, size);
                                                                                                            printf("into a binary heap\ndone...\n");
#endif
    b_heap* h = malloc(sizeof(b_heap));
    h->size = size;
    h->capacity = size;
    h->array = array;
    int i;
    for(i = closest_lower_p2(h->size) - 1; i >=0; i--)
        siftDown(h, i);
#if DEBUG_MODE
                                                                                                            heap_print(h);
                                                                                                            printf("done...\n");
#endif
    return h;
}

//----------------------------------------------------------------------------------------
void heap_sort(int * array, int size) {
    b_heap* h = array2heap(array, size);
    while(size >= 1)
    {
        array[--size] = heap_poll(h);
    }
    free(h);
}

//----------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------
inline void array_fill_with_rand(int* array, unsigned size)
{
    unsigned i;
    for(i = 0; i < size; i++)
        array[i] = rand();
}

int heap_sort_test()
{
    unsigned u, w;
    int array[HEAP_SORT_TEST_ARRAY_SIZE];
    for(u = 0; u < HEAP_SORT_TEST_TEST_TIMES; u++)
    {
        array_fill_with_rand(array, HEAP_SORT_TEST_ARRAY_SIZE);

#if DEBUG_MODE
                                                                                                            printf("Array n%d before sorting:\n", u);
                                                                                                            array_print(array, HEAP_SORT_TEST_ARRAY_SIZE);
#endif

        heap_sort(array, HEAP_SORT_TEST_ARRAY_SIZE);

#if DEBUG_MODE
                                                                                                            printf("Array n%d after sorting:\n", u);
                                                                                                            array_print(array, HEAP_SORT_TEST_ARRAY_SIZE);
#endif

        for(w = 0; w <  HEAP_SORT_TEST_ARRAY_SIZE - 1; w++)
            if(array[w] > array[w+1])
            {
                printf("Test n.%d failed...\n(%d is higher than %d)\nAbort...", u, array[w], array[w+1]);
                return 0;
            }
        printf("Test n.%d passed...\n", u);
    }
    printf("All test passed, nice job!\n");
    return 1;
}
int main()
{
    heap_sort_test();
    return 1;
}

Это вывод (я удалил «возврат 0» в heap_sort_test(), чтобы получить больше данных, с ним он блокируется с первой попытки):

Array n0 before sorting:
[1804289383, 846930886, 1681692777, 1714636915, 1957747793, 424238335, 719885386, 1649760492, 596516649, 1189641421, ]
Making the array
[1804289383, 846930886, 1681692777, 1714636915, 1957747793, 424238335, 719885386, 1649760492, 596516649, 1189641421, ]
into a binary heap
done...
BINARY HEAP:
(size 10)
<1804289383>    
<846930886>    <1681692777>    
<1714636915>    <1957747793>    <424238335>    <719885386>    
<1649760492>    <596516649>    <1189641421>    <4195760>    
done...
Array n0 after sorting:
[846930886, 1681692777, 1714636915, 1957747793, 424238335, 719885386, 1649760492, 596516649, 1189641421, 1804289383, ]
Test n.0 failed...
(1957747793 is higher than 424238335)...
Test n.0 failed...
(1649760492 is higher than 596516649)...
Test n.0 passed...
Array n1 before sorting:
[1025202362, 1350490027, 783368690, 1102520059, 2044897763, 1967513926, 1365180540, 1540383426, 304089172, 1303455736, ]
Making the array
[1025202362, 1350490027, 783368690, 1102520059, 2044897763, 1967513926, 1365180540, 1540383426, 304089172, 1303455736, ]
into a binary heap
done...
BINARY HEAP:
(size 10)
<1025202362>    
<1350490027>    <783368690>    
<1102520059>    <2044897763>    <1967513926>    <1365180540>    
<1540383426>    <304089172>    <1303455736>    <4195760>    
done...
Array n1 after sorting:
[1350490027, 783368690, 1102520059, 2044897763, 1967513926, 1365180540, 1540383426, 304089172, 1303455736, 1025202362, ]
Test n.1 failed...
(1350490027 is higher than 783368690)...
Test n.1 failed...
(2044897763 is higher than 1967513926)...
Test n.1 failed...
(1967513926 is higher than 1365180540)...
Test n.1 failed...
(1540383426 is higher than 304089172)...
Test n.1 failed...
(1303455736 is higher than 1025202362)...
Test n.1 passed...
Array n2 before sorting:
[35005211, 521595368, 294702567, 1726956429, 336465782, 861021530, 278722862, 233665123, 2145174067, 468703135, ]
Making the array
[35005211, 521595368, 294702567, 1726956429, 336465782, 861021530, 278722862, 233665123, 2145174067, 468703135, ]
into a binary heap
done...
BINARY HEAP:
(size 10)
<35005211>    
<521595368>    <294702567>    
<1726956429>    <336465782>    <861021530>    <278722862>    
<233665123>    <2145174067>    <468703135>    <4195760>    
done...
Array n2 after sorting:
[521595368, 294702567, 1726956429, 336465782, 861021530, 278722862, 233665123, 2145174067, 468703135, 35005211, ]
Test n.2 failed...
(521595368 is higher than 294702567)...
Test n.2 failed...
(1726956429 is higher than 336465782)...
Test n.2 failed...
(861021530 is higher than 278722862)...
Test n.2 failed...
(278722862 is higher than 233665123)...
Test n.2 failed...
(2145174067 is higher than 468703135)...
Test n.2 failed...
(468703135 is higher than 35005211)...
Test n.2 passed...
Array n3 before sorting:
[1101513929, 1801979802, 1315634022, 635723058, 1369133069, 1125898167, 1059961393, 2089018456, 628175011, 1656478042, ]
Making the array
[1101513929, 1801979802, 1315634022, 635723058, 1369133069, 1125898167, 1059961393, 2089018456, 628175011, 1656478042, ]
into a binary heap
done...
BINARY HEAP:
(size 10)
<1101513929>    
<1801979802>    <1315634022>    
<635723058>    <1369133069>    <1125898167>    <1059961393>    
<2089018456>    <628175011>    <1656478042>    <4195760>    
done...
Array n3 after sorting:
[1801979802, 1315634022, 635723058, 1369133069, 1125898167, 1059961393, 2089018456, 628175011, 1656478042, 1101513929, ]
Test n.3 failed...
(1801979802 is higher than 1315634022)...
Test n.3 failed...
(1315634022 is higher than 635723058)...
Test n.3 failed...
(1369133069 is higher than 1125898167)...
Test n.3 failed...
(1125898167 is higher than 1059961393)...
Test n.3 failed...
(2089018456 is higher than 628175011)...
Test n.3 failed...
(1656478042 is higher than 1101513929)...
Test n.3 passed...
Array n4 before sorting:
[1131176229, 1653377373, 859484421, 1914544919, 608413784, 756898537, 1734575198, 1973594324, 149798315, 2038664370, ]
Making the array
[1131176229, 1653377373, 859484421, 1914544919, 608413784, 756898537, 1734575198, 1973594324, 149798315, 2038664370, ]
into a binary heap
done...
BINARY HEAP:
(size 10)
<1131176229>    
<1653377373>    <859484421>    
<1914544919>    <608413784>    <756898537>    <1734575198>    
<1973594324>    <149798315>    <2038664370>    <4195760>    
done...
Array n4 after sorting:
[1653377373, 859484421, 1914544919, 608413784, 756898537, 1734575198, 1973594324, 149798315, 2038664370, 1131176229, ]
Test n.4 failed...
(1653377373 is higher than 859484421)...
Test n.4 failed...
(1914544919 is higher than 608413784)...
Test n.4 failed...
(1973594324 is higher than 149798315)...
Test n.4 failed...
(2038664370 is higher than 1131176229)...
Test n.4 passed...
Array n5 before sorting:
[1129566413, 184803526, 412776091, 1424268980, 1911759956, 749241873, 137806862, 42999170, 982906996, 135497281, ]
Making the array
[1129566413, 184803526, 412776091, 1424268980, 1911759956, 749241873, 137806862, 42999170, 982906996, 135497281, ]
into a binary heap
done...
BINARY HEAP:
(size 10)
<1129566413>    
<184803526>    <412776091>    
<1424268980>    <1911759956>    <749241873>    <137806862>    
<42999170>    <982906996>    <135497281>    <4195760>    
done...
Array n5 after sorting:
[184803526, 412776091, 1424268980, 1911759956, 749241873, 137806862, 42999170, 982906996, 135497281, 1129566413, ]
Test n.5 failed...
(1911759956 is higher than 749241873)...
Test n.5 failed...
(749241873 is higher than 137806862)...
Test n.5 failed...
(137806862 is higher than 42999170)...
Test n.5 failed...
(982906996 is higher than 135497281)...
Test n.5 passed...
Array n6 before sorting:
[511702305, 2084420925, 1937477084, 1827336327, 572660336, 1159126505, 805750846, 1632621729, 1100661313, 1433925857, ]
Making the array
[511702305, 2084420925, 1937477084, 1827336327, 572660336, 1159126505, 805750846, 1632621729, 1100661313, 1433925857, ]
into a binary heap
done...
BINARY HEAP:
(size 10)
<511702305>    
<2084420925>    <1937477084>    
<1827336327>    <572660336>    <1159126505>    <805750846>    
<1632621729>    <1100661313>    <1433925857>    <4195760>    
done...
Array n6 after sorting:
[2084420925, 1937477084, 1827336327, 572660336, 1159126505, 805750846, 1632621729, 1100661313, 1433925857, 511702305, ]
Test n.6 failed...
(2084420925 is higher than 1937477084)...
Test n.6 failed...
(1937477084 is higher than 1827336327)...
Test n.6 failed...
(1827336327 is higher than 572660336)...
Test n.6 failed...
(1159126505 is higher than 805750846)...
Test n.6 failed...
(1632621729 is higher than 1100661313)...
Test n.6 failed...
(1433925857 is higher than 511702305)...
Test n.6 passed...
Array n7 before sorting:
[1141616124, 84353895, 939819582, 2001100545, 1998898814, 1548233367, 610515434, 1585990364, 1374344043, 760313750, ]
Making the array
[1141616124, 84353895, 939819582, 2001100545, 1998898814, 1548233367, 610515434, 1585990364, 1374344043, 760313750, ]
into a binary heap
done...
BINARY HEAP:
(size 10)
<1141616124>    
<84353895>    <939819582>    
<2001100545>    <1998898814>    <1548233367>    <610515434>    
<1585990364>    <1374344043>    <760313750>    <4195760>    
done...
Array n7 after sorting:
[84353895, 939819582, 2001100545, 1998898814, 1548233367, 610515434, 1585990364, 1374344043, 760313750, 1141616124, ]
Test n.7 failed...
(2001100545 is higher than 1998898814)...
Test n.7 failed...
(1998898814 is higher than 1548233367)...
Test n.7 failed...
(1548233367 is higher than 610515434)...
Test n.7 failed...
(1585990364 is higher than 1374344043)...
Test n.7 failed...
(1374344043 is higher than 760313750)...
Test n.7 passed...
All test passed, nice job!

c binary-heap heapsort
person user2704673    schedule 11.05.2018    source источник
comment
#ifdef DEBUG_MODE .... #endif должен вырезать отладочные отпечатки, когда я решаю проблему (я говорю это, потому что не знаю, является ли это обычной практикой или вообще полезно)   -  person user2704673    schedule 11.05.2018
comment
разбейте его на этапы и попытайтесь сузить круг своей проблемы. И пройдитесь по коду в отладчике и проверьте, что происходит там, где что-то начинает идти не так.   -  person Christian Gibbons    schedule 11.05.2018
comment
Я не знаю, как использовать отладчик, кроме базового распределения и освобождения памяти с помощью valgrind и анализа ошибок сегментации с помощью gdb.   -  person user2704673    schedule 11.05.2018
comment
Но похоже, что array2heap(), который должен превратить массив в кучу, вообще ничего не делает.   -  person user2704673    schedule 11.05.2018
comment
Тогда это будет прекрасная возможность научиться использовать gdb.   -  person Christian Gibbons    schedule 11.05.2018
comment
Как мне его использовать? На что оно способно в этой ситуации? Я спрашиваю, чтобы знать, чему учиться   -  person user2704673    schedule 11.05.2018
comment
Вы можете выполнять код построчно, проверять состояние переменных и в интерактивном режиме видеть точный ход программы. Эта ссылка, по-видимому, популярна, чтобы научить людей отлаживать: ericlippert.com/2014/03/05/how-to-debug-small-programs   -  person Christian Gibbons    schedule 11.05.2018
comment
Обратите внимание, что у вас слишком много и слишком мало скобок в #define right_child_index(i) (((i + 1) << 1)). У вас слишком много, потому что вам не нужны двойные скобки вокруг всего выражения; у вас слишком мало, потому что у вас нет скобок вокруг i. Вам нужно #define right_child_index(i) (((i) + 1) << 1). При работе с макросами для арифметики необходимо заключать каждый аргумент в круглые скобки в расширении, чтобы защититься от неверного толкования. Аналогичные комментарии относятся и к другим макросам.   -  person Jonathan Leffler    schedule 12.05.2018
comment
Исправил, но вывод остался прежним (знаю, что это потенциальная ошибка, которую нужно было исправить, но это было не так)   -  person user2704673    schedule 12.05.2018
comment
ссылка на руководство по gdb   -  person user3629249    schedule 13.05.2018
comment
инструмент ddd создан поверх gdb для обеспечения визуального интерфейса. руководство по DDD   -  person user3629249    schedule 13.05.2018

Ответы (1)


arrow_upward
1
arrow_downward

(отвечая на мой собственный вопрос)

Макрос is_higher(a, b) должен был представлять порядок. Должно быть (((a)>(b))? 1 : 0), то есть должно быть 1 (истина), когда a больше b, 0 (ложь) в противном случае.

Указатель на функцию был бы гораздо лучшим выбором, поскольку он:

А) менее подвержен ошибкам

Б) более гибкий (можно было бы изменить порядок во время выполнения)

person user2704673    schedule 17.07.2018
comment
is_higher ((a)›(b)) будет достаточно. это уже правда или ложь. - person Max; 17.07.2018
comment
Действительно, мой ответ был излишним - person user2704673; 17.07.2018