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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
#include <stdio.h>
#include <stdlib.h>
typedef void *HeapEle;
typedef int (*HeapCmp)(const void *a, const void *b);
int cmp_int_asc(const void *pa, const void *pb) {
int *a = *(int **)pa;
int *b = *(int **)pb;
if (*a < *b) {
return -1;
} else if (*a > *b) {
return 1;
} else {
return 0;
}
}
int cmp_int_desc(const void *a, const void *b) { return -cmp_int_asc(a, b); }
typedef struct {
int point; // 得分
int win; // 胜场
} Player;
int cmp_player_desc(const void *pa, const void *pb) {
Player *a = *(Player **)pa;
Player *b = *(Player **)pb;
if (a->point != b->point) {
return b->point - a->point; // 按得分降序
} else {
return b->win - a->win; // 得分相同按胜场多的排前面
}
}
typedef struct {
HeapEle *data;
int size;
int capacity;
HeapCmp cmp; // 比较函数指针
} Heap;
void swap(HeapEle *a, HeapEle *b) {
HeapEle tmp = *a;
*a = *b;
*b = tmp;
}
Heap *HeapInit(int capacity, HeapCmp cmp) {
Heap *h = malloc(sizeof(Heap));
h->data = malloc(sizeof(HeapEle) * capacity);
h->size = 0;
h->capacity = capacity;
h->cmp = cmp;
return h;
}
void HeapFree(Heap *h) {
if (!h)
return;
free(h->data);
free(h);
}
/*******
* 参数：h：堆指针
* idx：要上浮的元素下标
* 返回值：上浮后的元素下标
* 说明：将下标为idx的元素上浮到合适位置
*******/
void heap_up(Heap *h, int idx) {
while (idx > 0) {
int parent = (idx - 1) >> 1;
if (h->cmp(&h->data[idx], &h->data[parent]) < 0) {
swap(&h->data[idx], &h->data[parent]);
idx = parent;
} else
break;
}
}
/******
* 参数：h：堆指针
* idx：要下沉的元素下标
* 返回值：下沉后的元素下标
* 说明：将下标为idx的元素下沉到合适位置
*******/
void heap_down(Heap *h, int idx) {
while (1) {
int l = (idx << 1) + 1, r = (idx << 1) + 2,
best = idx; // min改名best，意味选最大选最小
if (l < h->size && h->cmp(&h->data[best], &h->data[l]) > 0) {
best = l;
}
if (r < h->size && h->cmp(&h->data[best], &h->data[r]) > 0) {
best = r;
}
if (best != idx) {
swap(&h->data[best], &h->data[idx]);
idx = best;
} else
break;
}
}
void *HeapPush(Heap *h, HeapEle ele) {
if (h->size == h->capacity) {
h->capacity *= 2;
h->data = realloc(h->data, h->capacity * sizeof(HeapEle));
}
h->data[h->size] = ele;
heap_up(h, h->size);
h->size++;
}
HeapEle HeapPop(Heap *h) {
HeapEle ret = h->data[0];
h->data[0] = h->data[--h->size];
heap_down(h, 0);
return ret;
}
int main() {
// Test Int Heap
Heap *h = HeapInit(4, cmp_int_asc); // 创建一个容量为4的最小堆
int testIntHeapArr[] = {512, 343, 81, 154, 142, 742, 14, 51};
for (int i = 0; i < sizeof(testIntHeapArr) / sizeof(testIntHeapArr[0]);
i++) {
HeapPush(h, &testIntHeapArr[i]);
}
printf("Int in sorted order:\n");
while (h->size > 0) {
int *val = (int *)HeapPop(h);
printf("%d ", *val);
}
printf("\n");
HeapFree(h);
// Test Player Heap
Heap *ph = HeapInit(4, cmp_player_desc); // 创建一个容量为4的最大堆
Player players[] = {{14, 5}, {12, 3}, {12, 7}, {20, 10}, {15, 5}, {10, 5}};
for (int i = 0; i < sizeof(players) / sizeof(players[0]); i++) {
HeapPush(ph, &players[i]);
}
printf("Players in sorted order (by point desc, win desc):\n");
while (ph->size > 0) {
Player *p = (Player *)HeapPop(ph);
printf("Point: %d, Win: %d\n", p->point, p->win);
}
HeapFree(ph);
return 0;
}
|