heap-sort
基本操作a, push_heap，将新元素加入heap中。做法是先将元素加至序列最后，然后逐渐向上交换，直到到达合适位置，即所谓sift-up操作。
基本操作b, pop_heap，从堆中删除根元素。做法是先将根元素交换至最后（待删除位置），然后调整新的根到合适位置，即所谓sift-down操作。
基本操作c，make_heap，调整一个随机序列使其满足堆结构。
以上三个基本操作STL中就有提供，用这三个基本操作，可以直接搞出heap-sort了。实际上，heap-sort只需要make_heap和pop_heap即可。push_heap在实现类似priority_queue的时候会有用。
用STL的make_heap与pop_heap来实现heap-sort：
View Code
1 #include <cstdio>
2 #include <algorithm>
3
4 #define MAX_N 20
5 int arr[MAX_N];
6
7 void print_arr(void)
8 {
9 int i;
10 for (i = 0; i < MAX_N; i++)
11 std::printf("%d ", arr[i]);
12 std::printf("\n");
13 }
14
15 int main(int argc, char *argv[])
16 {
17 int i;
18 for (i = 0; i < MAX_N; i++)
19 arr[i] = i;
20 //print_arr();
21 std::random_shuffle(arr, arr + MAX_N);
22 //print_arr();
23 std::make_heap(arr, arr + MAX_N);
24 //print_arr();
25 for (i = MAX_N; i > 0; i--) {
26 std::pop_heap(arr, arr + i);
27 }
28 //print_arr();
29
30 return 0;
31 }
make_heap的实现：即构建满足heap结构的隐式二叉树。可以自顶向下建立，这是一个从左向右循环调用push_heap的过程。复杂度更低的是自底而上建立，这是因为后一半节点都是叶子节点，只需从后向前，每次加入一个根节点并调节位置即可（sift-down）。
sift_down的实现：略。
heap_sort的实现：与上面的STL版类似。
放到一起，heap_sort的实现：
View Code
1 #include <string.h> /* memcpy */
2 #include <stdlib.h> /* ssize_t */
3
4 #define SWAP_ELEM(pl, pr, size) do {\
5 char temp[size]; /* C99 */ \
6 memcpy(temp, pl, size); \
7 memcpy(pl, pr, size); \
8 memcpy(pr, temp, size); \
9 } while (0)
10
11 // find the appropriate place for the specified node and put it there.
12 static void sift_down(char *base, size_t nmemb, size_t curr_idx, size_t size,
13 int(*compare_func)(const void *, const void *))
14 {
15 if (nmemb <= 1)
16 return;
17
18 while (curr_idx < nmemb) { // sift-down arr[curr_idx].
19 char *curr = base + curr_idx * size;
20 char *max = curr;
21 size_t max_idx = curr_idx;
22 // find the greatest of (curr, left(curr), right(curr))
23 size_t left_idx = curr_idx * 2 + 1;
24 char *pl = base + left_idx * size;
25 if ((left_idx < nmemb) && (compare_func(pl, max) > 0)) { // *pl is greater than *max.
26 max = pl;
27 max_idx = left_idx;
28 }
29 size_t right_idx = curr_idx * 2 + 2;
30 char *pr = base + right_idx * size;
31 if ((right_idx < nmemb) && (compare_func(pr, max) > 0)) { // *pr is greater than *max.
32 max = pr;
33 max_idx = right_idx;
34 }
35 if (max_idx == curr_idx) {
36 break;
37 } else { // turn into left or right subtree.
38 SWAP_ELEM(curr, max, size);
39 curr_idx = max_idx;
40 }
41 }
42 }
43
44 static void my_make_heap(char *base, size_t nmemb, size_t size,
45 int(*compare_func)(const void *, const void *))
46 {
47 if (nmemb <= 1)
48 return;
49
50 ssize_t i = nmemb / 2 - 1; // size_t will fail due to its unsigned-ness.
51 for (; i >= 0; i--) { // build the heap bottom-up
52 sift_down(base, nmemb, i, size, compare_func);
53 }
54 }
55
56 /* Implementation of heap-sort, following a libc-qsort-like interface. */
57 void my_heapsort(void *base, size_t nmemb, size_t size,
58 int(*compare_func)(const void *, const void *))
59 {
60 char *pbase = base;
61
62 my_make_heap(pbase, nmemb, size, compare_func);
63
64 size_t curr_last_idx = nmemb - 1;
65 while (curr_last_idx > 0) {
66 char *curr_last = pbase + curr_last_idx * size;
67 SWAP_ELEM(pbase, curr_last, size);
68 --curr_last_idx;
69 // sift the new root node to its place.
70 sift_down(pbase, curr_last_idx + 1, 0, size, compare_func);
71 }
72 }
73
74 #undef SWAP_ELEM
heap_sort的测试代码：
View Code
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <time.h>
4
5 extern void my_heapsort(void *base, size_t nmemb, size_t size,
6 int(*compare_func)(const void *, const void *));
7
8 #define MAX_N 27
9 int arr[MAX_N];
10
11 void print_arr(void)
12 {
13 int i;
14
15 for (i = 0; i < MAX_N; i++)
16 printf("%d ", arr[i]);
17 printf("\n");
18 }
19
20 /* A simplified version of the STL algorithm random_shuffle */
21 void my_random_shuffle(int *arr, int n)
22 {
23 int i;
24
25 srand(time(0));
26 for (i = 1; i < n; i++) {
27 int selected_index = rand() % (i + 1); // OK, forgive my using rand(),
28 //which is of limited random digits.
29 int temp = arr[selected_index]; // swap to current position.
30 arr[selected_index] = arr[i];
31 arr[i] = temp;
32 }
33 /* equivalent to:
34 for (i = n - 1; i > 0; i--) {
35 int selected_index = rand() % (i + 1); // select a random element.
36 int temp = arr[selected_index]; // swap to current position.
37 arr[selected_index] = arr[i];
38 arr[i] = temp;
39 }
40 */
41 }
42
43 int comp(const void *lhs, const void *rhs)
44 {
45 return *(int *)lhs - *(int *)rhs;
46 }
47
48 int main(int argc, char *argv[])
49 {
50 int i;
51
52 setbuf(stdout, NULL);
53
54 for (i = 0; i < MAX_N; i++)
55 arr[i] = MAX_N - 1 - i;
56 // case #1, sequence of 1 element
57 printf("case #1: \n");
58 my_heapsort(arr, 1, sizeof(arr[0]), comp);
59 print_arr();
60 // case #2, sequence of 2 elements
61 printf("case #2: \n");
62 my_heapsort(arr, 2, sizeof(arr[0]), comp);
63 print_arr();
64 // case #3, sequence of 3 elements
65 printf("case #3: \n");
66 my_heapsort(arr, 3, sizeof(arr[0]), comp);
67 print_arr();
68
69 // case #4, all 0's
70 printf("case #4: \n");
71 for (i = 0; i < MAX_N; i++)
72 arr[i] = 0;
73 my_heapsort(arr, MAX_N, sizeof(arr[0]), comp);
74 print_arr();
75
76 // case #5, ascent sequence.
77 printf("case #5: \n");
78 for (i = 0; i < MAX_N; i++)
79 arr[i] = i;
80 my_heapsort(arr, MAX_N, sizeof(arr[0]), comp);
81 print_arr();
82
83 // case #6, descent sequence.
84 printf("case #6: \n");
85 for (i = 0; i < MAX_N; i++)
86 arr[i] = MAX_N - 1 - i;
87 my_heapsort(arr, MAX_N, sizeof(arr[0]), comp);
88 print_arr();
89
90 // case #7, random permutated sequence.
91 printf("case #7: \n");
92 for (i = 0; i < MAX_N; i++)
93 arr[i] = i;
94 my_random_shuffle(arr, MAX_N);
95 print_arr();
96 //qsort(arr, MAX_N, sizeof(arr[0]), comp);
97 //print_arr();
98 my_heapsort(arr, MAX_N, sizeof(arr[0]), comp);
99 print_arr();
100
101 return 0;
102 }