我将堆排序作为使用给定二进制堆 API 的练习来实现，并且做得很好。然后我尝试从头开始实现它并失败了。 该算法应该给定一个大小为 n 的数组，将其放入一个二叉堆中并具有 O(logN) 的复杂度；然后继续提取根(最大元素)，将其放在数组的末尾并重置堆属性。 无论如何，它就是行不通，我不明白为什么。这是代码:
#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;
}
这是输出(我删除了 heap_sort_test() 中的“return 0”以获得更多数据，它在第一次尝试时阻塞):
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!
最佳答案
(回答我自己的问题)
宏 is_higher(a, b) 用于表示顺序。它应该是 (((a)>(b))? 1 : 0)，即当 a 大于 b 时它应该是 1(真)，否则是 0(假)。
指向函数的指针会是更好的选择，因为它:
A) 不易出错
B) 更灵活(可以在运行时更改顺序)
关于C实现heapsort不改变数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50299518/