LeetCode/LeetCode-295.c at master · hello-sources/LeetCode · GitHub

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
/*************************************************************************
    > File Name: LeetCode-295.c
    > Author: ltw
    > Mail: 3245849061@qq.com
    > Created Time: Thu 21 May 2020 10:42:36 PM CST
 ************************************************************************/


typedef struct Heap {
    int *data;
    int n, size;
} Heap;

void expandHeap(Heap *h) {
    h->data = realloc(h->data, 2 * h->size * sizeof(int));
    h->size *= 2;
    return ;
}

#define swap(a, b) { \
    __typeof(a) __temp = a; \
    a = b, b = __temp; \
}

#define pushHeap(h, val, comp) { \
    if (h->size == h->n + 1) { \
        expandHeap(h); \
    } \
    h->data[++(h->n)] = val; \
    int ind = h->n; \
    while (ind != 1 && h->data[ind] comp h->data[ind >> 1]) { \
        swap(h->data[ind], h->data[ind >> 1]); \
        ind >>= 1; \
    } \
}

#define popHeap(h, comp) do { \
    if (h->n == 0) break; \
    h->data[1] = h->data[(h->n)--]; \
    int ind = 1; \
    while (ind << 1 <= h->n) { \
        int temp = ind, l = ind << 1, r = ind << 1 | 1; \
        if (h->data[l] comp h->data[temp]) temp = l; \
        if (r <= h->n && h->data[r] comp h->data[temp]) temp = r; \
        if (temp == ind) break; \
        swap(h->data[temp], h->data[ind]); \
        ind = temp; \
    } \
} while(0);

Heap *creatHeap() {
    Heap *h = (Heap *)malloc(sizeof(Heap));
    h->size = 100;
    h->data = (int *)malloc(sizeof(int) * h->size);
    h->n = 0;
    return h;
}

void clearHeap(Heap *h) {
    if (h == NULL) return ;
    free(h->data);
    free(h);
    return ;
}

typedef struct {
    Heap *min_heap, *max_heap;
} MedianFinder;

/** initialize your data structure here. */

MedianFinder* medianFinderCreate() {
    MedianFinder* m = (MedianFinder*)malloc(sizeof(MedianFinder));
    m->min_heap = creatHeap();
    m->max_heap = creatHeap();
    return m;
}

void medianFinderAddNum(MedianFinder* m, int num) {
    if (m->min_heap->n == 0 || num >= m->min_heap->data[1]) {
        pushHeap(m->min_heap, num, <);
    } else {
        pushHeap(m->max_heap, num, >);
    }
    if (m->min_heap->n - m->max_heap->n == 2) {
        pushHeap(m->max_heap, m->min_heap->data[1], >);
        popHeap(m->min_heap, <);
    }
    if (m->max_heap->n - m->min_heap->n == 2) {
        pushHeap(m->min_heap, m->max_heap->data[1], <);
        popHeap(m->max_heap, >);
    }
    return ;
}

double medianFinderFindMedian(MedianFinder* m) {
    switch (m->min_heap->n - m->max_heap->n) {
        case -1: return m->max_heap->data[1];
        case 0: return 1.0 * (m->min_heap->data[1] + m->max_heap->data[1]) / 2.0;
        case 1: return m->min_heap->data[1];
    }
    return 0.0;
}

void medianFinderFree(MedianFinder* obj) {
    if (obj == NULL) return ;
    clearHeap(obj->min_heap);
    clearHeap(obj->max_heap);
    free(obj);
    return ;
}