본문으로 바로가기

Expert하면서 ~.h를 코딩할 일은 없으니까..

그냥 한 코드에 다 넣고 코딩해봤다.

이제 여러번 하니까 손에 익은 듯 하다.



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
#include <stdio.h>
#include <stdlib.h>
template <class T>
struct Vector{
    int sz,idx;
    T *arr;
    Vector():sz(1),idx(0){
        arr = (T*)malloc(sizeof(T));
    }
    ~Vector() {
        if(arr) free(arr);
    }
 
    //private functions
    void expand(int& size) {
        size*=2;
        do { arr = (T*)realloc(arr, size*sizeof(T)); } while(arr==NULL);
    }
 
    //public functions
    void push_back(const T& x) {
        if(idx>=sz) expand(sz);
        arr[idx++= x;
    }
    void pop_back() {
        idx--;
    }
    bool empty() { return idx==0; }
    int size() { return idx; }
    void clear() { idx=0; }
    T& operator[](const int at) const { return arr[at]; }
};
 
template <class T>
struct Less{
    bool operator()(const T& lhs, const T& rhs) const {
        return lhs<rhs;
    }
};
template <class T>
struct Greater{
    bool operator()(const T& lhs, const T& rhs) const {
        return rhs<lhs;
    }
};
 
 
template <class T, class Container = Vector<T>class Cmp = Less<T> >
struct Heap{
    int sz;
    Container v;
    Cmp cmp;
 
    Heap():sz(0) {
        v.clear();
        v.push_back(T(0));
    }
 
    void swap(T& x, T& y) {
        T tmp=x; x=y; y=tmp;
    }
    void push(const T& x) {
        v.push_back(x); sz++;
        up(v.size()-1);
    }
    void up(int at) {
        if(at<=1return;
        int par = at/2;
        if(cmp(v[par],v[at])) {
            swap(v[par], v[at]);
            up(par);
        }
    }
 
    void pop() {
        v[1]=v[sz]; v.pop_back(); sz--;
        down(1);
    }
    void down(int at) {
        int l=at*2, r=at*2+1, pos=at;
        if(l<=sz) if(cmp(v[pos],v[l])) pos=l;
        if(r<=sz) if(cmp(v[pos],v[r])) pos=r;
        if(pos!=at) {
            swap(v[at],v[pos]);
            down(pos);
        }
    }
    T top() const {
        if(sz<=0) exit(1);
        return v[1];
    }
 
    int size() { return sz; }
    bool empty() { return sz<=0; }
    void clear() {
        sz=0;
        v.clear();
    }
};
 
Heap<int> mxh;
Heap<int, Vector<int>, Greater<int> > mnh;
 
int main() {
    freopen("input2.txt""r", stdin);
    int n; scanf("%d"&n);
    for(int i=0; i<n; i++) {
        int x; scanf("%d"&x);
        mxh.push(x);
        mnh.push(x);
        printf("MXH LIST: ");
        for(int i=1; i<=mxh.sz; i++printf("%d ", mxh.v[i]);
        puts("");
        printf("MNH LIST: ");
        for(int i=1; i<=mnh.sz; i++printf("%d ", mnh.v[i]);
        puts("");
        if(i%== 4) {
            mxh.pop();
            mnh.pop();
        }
    }
    printf("MaxHeap: ");
    while(!mxh.empty()) {
        int top = mxh.top(); mxh.pop();
        printf("%d ", top);
    }
    puts("");
    printf("MinHeap: ");
    while(!mnh.empty()) {
        int top = mnh.top(); mnh.pop();
        printf("%d ",top);
    }
    puts("");
    return 0;
}
cs

댓글을 달아 주세요