HeapTree

홍진호·2022년 12월 5일
CheapTree라이브러리백준클래스
0

언젠가 만들어질 홍진호 라이브러리

목록 보기
4/4
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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
public class HeapTree
    {
        List<int> heap;
        public bool maxHeap;
 
        public int popHeap()
        {
 
            if(heap == null)
            {
                heap = new List<int>();
                heap.Add(-1);
            }
            //for (int i = 0; i < heap.Count; i++)
            //{
            //    Console.WriteLine("HeapList : " + heap[i] + " ");
            //}
            if (heap.Count < 2)
            {
                return 0;
            }
            int pop = heap[1];
            heap[1] = heap[heap.Count - 1];
            heap.RemoveAt(heap.Count - 1);
            int me = 1;
            int insert = 1;
            while (insert != 0)
            {
                insert = checkChild(insert);
                if(insert != 0)
                {
                    swap(me, insert);
                }
                me = insert;
            }
            return pop;
        }
 
        int checkChild(int idx)
        {
            int re = 0;
            if (maxHeap)
            {
                if (heap.Count - 1 >= idx * 2 + 1)
                {
                    if (heap[idx * 2] >heap[idx * 2 + 1])
                    {
                        re = idx * 2;
                    }
                    else
                    {
                        re = idx * 2 + 1;
                    }
                    if (heap[re] > heap[idx])
                    {
                        return re;
                    }
                    else
                    {
                        return 0;
                    }
                }
                else if (heap.Count - 1 >= idx * 2)
                {
                    re = heap[idx * 2];
                    if (re > heap[idx])
                    {
                        return idx *2;
                    }
                    else
                    {
                        return 0;
                    }
                }
                else
                {
                    return 0;
                }
            }
            else
            {
                if(heap.Count -1 >= idx *2 + 1)
                {
                    if(heap[idx *2] < heap[idx *2 + 1])
                    {
                        re = idx * 2;
                    }
                    else
                    {
                        re = idx * 2 + 1;
                    }
                    if (heap[re] < heap[idx])
                    {
                        return re;
                    }
                    else
                    {
                        return 0;
                    }
                }
                else if(heap.Count - 1 >= idx * 2)
                {
                    re = heap[idx * 2];
                    if (re < heap[idx])
                    {
                        return idx *2;
                    }
                    else
                    {
                        return 0;
                    }
                }
                else
                {
                    return 0;
                }
 
            }
        }
        public void addHeap(int data)
        {
            if (heap == null)
            {
                heap = new List<int>();
                heap.Add(-1); 
                heap.Add(data); 
            }
            else
            {
                heap.Add(data);
                int parent, insert = heap.Count - 1;
                if (maxHeap)
                {
                    while (isup(insert))
                    {
                        parent = insert / 2;
                        swap(insert, parent);
                        insert = parent;
                    }
                }
                else
                {
                    while (isdown(insert))
                    {
                        parent = insert / 2;
                        swap(insert, parent);
                        insert = parent;
                    }
                }
            }
        }
        bool isup(int insert)
        {
            if (insert <= 1) 
            {
                return false;
            }
            if (heap[insert / 2] < heap[insert])
            {
                return true;
            }
            else
            {
                return false;
            }        
        }
        bool isdown(int insert)
        {
            if(heap[insert/2] < 0)
            {
                return false;
            }
            if(heap[insert/2] >heap[insert])
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        void swap(int i1, int i2)
        {
            int temp = heap[i1];
            heap[i1] = heap[i2];
            heap[i2] = temp;
        }
 
    }
cs

어제 백준 1927번 풀기위해 만들었던 힙 트리이다. 힙 트리는 이제 여러 배열들 안에서 가장 큰 값이나 가장 작은 값을 빠르게 찾기 위해서 사용하는 자료구조인데 자세한건 나무위키에 검색해서 보도록하자. 나도 나무위키 보고 공부해서 이해했다.

profile
홍진호
중앙대 예술공학과 홍진호
이전 포스트

DFS,BFS

0개의 댓글