Я реализовывал heapsort как упражнение с заданными 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;
}
Это вывод (я удалил «return 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!