1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
#include<stdio.h>
#include<stdlib.h>
#define HEAP_TYPE 0 // if 0 is max heap, else min heap
unsigned heapsize = 0;
int compare(int x, int y) {
return (!HEAP_TYPE) ? x < y : x > y;
}
void swap(int* a, int x, int y) {
int temp = a[x];
a[x] = a[y];
a[y] = temp;
}
void insert(int* a, int k) {
a[++heapsize] = k;
unsigned i = heapsize;
while(i > 1 && compare(a[i>>1], a[i])) {
swap(a, i, i >> 1);
i >>= 1;
}
}
void heapify(int* a, int n, int i) {
int l = i << 1;
int r = l | 1;
int max = i;
if(l <= n && !compare(a[l], a[max])) max = l;
if(r <= n && !compare(a[r], a[max])) max = r;
if(max != i) {
swap(a, i, max);
heapify(a, n, max);
}
}
void build(int* a, int n) {
for(unsigned i = n/2; i > 0; --i) {
heapify(a, n, i);
}
}
int extract(int* a) {
swap(a, 1, heapsize);
--heapsize;
heapify(a, heapsize, 1);
return *(a+heapsize+1);
}
int* heapsort(int* a, int n) {
int* b = malloc(sizeof(int) * n);
build(a, n);
for(unsigned i = 0; i < n; ++i) {
b[i] = extract(a);
}
return b;
}
void increase_key(int* a, int i, int k) {
swap(a, i, k);
while(i > 1 && compare(a[i>>1], a[i])) {
swap(a, i, i >> 1);
i >>= 1;
}
}
int main() {
heapsize = 6;
int* a = malloc(sizeof(int) * 7);
a[1] = 5;
a[2] = 24;
a[3] = 1;
a[4] = 12;
for(unsigned i = 1; i < 7; ++i)
printf("%d ", a[i]);
printf("\n");
build(a, 4);
for(unsigned i = 1; i < 7; ++i)
printf("%d ", a[i]);
printf("\n\n");
for(unsigned i = 1; i < 7; ++i)
a[i] = i;
build(a, 6);
for(unsigned i = 1; i <= heapsize; ++i)
printf("%d ", *(a+i));
printf("\n");
printf("max value = %d\n", extract(a));
for(unsigned i = 1; i <= heapsize; ++i)
printf("%d ", *(a+i));
printf("\n");
increase_key(a, 1, 4);
for(unsigned i = 1; i <= heapsize; ++i)
printf("%d ", *(a+i));
printf("\n");
int n = heapsize;
int* b = heapsort(a, heapsize);
printf("heapsort = ");
for(unsigned i = 0; i < n; ++i)
printf("%d ", *(b+i));
free(b);
free(a);
return 0;
}
|
