1/*
2 * ν (Heap)
3 * Min/Max Heap, Priority Queue, Heap Sort
4 *
5 * μ°μ μμ κΈ°λ°μ ν¨μ¨μ μΈ μλ£κ΅¬μ‘°μ
λλ€.
6 */
7
8#include <iostream>
9#include <vector>
10#include <queue>
11#include <algorithm>
12#include <functional>
13
14using namespace std;
15
16// =============================================================================
17// 1. μ΅μ ν ꡬν
18// =============================================================================
19
20class MinHeap {
21private:
22 vector<int> heap;
23
24 void heapifyUp(int idx) {
25 while (idx > 0) {
26 int parent = (idx - 1) / 2;
27 if (heap[parent] <= heap[idx]) break;
28 swap(heap[parent], heap[idx]);
29 idx = parent;
30 }
31 }
32
33 void heapifyDown(int idx) {
34 int size = heap.size();
35 while (true) {
36 int smallest = idx;
37 int left = 2 * idx + 1;
38 int right = 2 * idx + 2;
39
40 if (left < size && heap[left] < heap[smallest])
41 smallest = left;
42 if (right < size && heap[right] < heap[smallest])
43 smallest = right;
44
45 if (smallest == idx) break;
46 swap(heap[idx], heap[smallest]);
47 idx = smallest;
48 }
49 }
50
51public:
52 void push(int val) {
53 heap.push_back(val);
54 heapifyUp(heap.size() - 1);
55 }
56
57 int pop() {
58 if (heap.empty()) throw runtime_error("Heap is empty");
59 int minVal = heap[0];
60 heap[0] = heap.back();
61 heap.pop_back();
62 if (!heap.empty()) heapifyDown(0);
63 return minVal;
64 }
65
66 int top() const {
67 if (heap.empty()) throw runtime_error("Heap is empty");
68 return heap[0];
69 }
70
71 bool empty() const { return heap.empty(); }
72 size_t size() const { return heap.size(); }
73};
74
75// =============================================================================
76// 2. ν μ λ ¬
77// =============================================================================
78
79void heapify(vector<int>& arr, int n, int i) {
80 int largest = i;
81 int left = 2 * i + 1;
82 int right = 2 * i + 2;
83
84 if (left < n && arr[left] > arr[largest])
85 largest = left;
86 if (right < n && arr[right] > arr[largest])
87 largest = right;
88
89 if (largest != i) {
90 swap(arr[i], arr[largest]);
91 heapify(arr, n, largest);
92 }
93}
94
95void heapSort(vector<int>& arr) {
96 int n = arr.size();
97
98 // ν ꡬμ±
99 for (int i = n / 2 - 1; i >= 0; i--) {
100 heapify(arr, n, i);
101 }
102
103 // μΆμΆ
104 for (int i = n - 1; i > 0; i--) {
105 swap(arr[0], arr[i]);
106 heapify(arr, i, 0);
107 }
108}
109
110// =============================================================================
111// 3. Kλ²μ§Έ μμ
112// =============================================================================
113
114// λ°°μ΄μμ Kλ²μ§Έλ‘ ν° μμ
115int findKthLargest(vector<int>& nums, int k) {
116 priority_queue<int, vector<int>, greater<int>> minHeap;
117
118 for (int num : nums) {
119 minHeap.push(num);
120 if ((int)minHeap.size() > k) {
121 minHeap.pop();
122 }
123 }
124
125 return minHeap.top();
126}
127
128// λ°°μ΄μμ Kλ²μ§Έλ‘ μμ μμ
129int findKthSmallest(vector<int>& nums, int k) {
130 priority_queue<int> maxHeap;
131
132 for (int num : nums) {
133 maxHeap.push(num);
134 if ((int)maxHeap.size() > k) {
135 maxHeap.pop();
136 }
137 }
138
139 return maxHeap.top();
140}
141
142// =============================================================================
143// 4. μ€μκ° μ€νΈλ¦Ό
144// =============================================================================
145
146class MedianFinder {
147private:
148 priority_queue<int> maxHeap; // μμ μ λ°
149 priority_queue<int, vector<int>, greater<int>> minHeap; // ν° μ λ°
150
151public:
152 void addNum(int num) {
153 maxHeap.push(num);
154 minHeap.push(maxHeap.top());
155 maxHeap.pop();
156
157 if (minHeap.size() > maxHeap.size()) {
158 maxHeap.push(minHeap.top());
159 minHeap.pop();
160 }
161 }
162
163 double findMedian() {
164 if (maxHeap.size() > minHeap.size()) {
165 return maxHeap.top();
166 }
167 return (maxHeap.top() + minHeap.top()) / 2.0;
168 }
169};
170
171// =============================================================================
172// 5. Kκ° μ λ ¬ 리μ€νΈ λ³ν©
173// =============================================================================
174
175struct ListNode {
176 int val;
177 ListNode* next;
178 ListNode(int x) : val(x), next(nullptr) {}
179};
180
181ListNode* mergeKLists(vector<ListNode*>& lists) {
182 auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
183 priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
184
185 for (ListNode* list : lists) {
186 if (list) pq.push(list);
187 }
188
189 ListNode dummy(0);
190 ListNode* curr = &dummy;
191
192 while (!pq.empty()) {
193 ListNode* node = pq.top();
194 pq.pop();
195 curr->next = node;
196 curr = curr->next;
197 if (node->next) pq.push(node->next);
198 }
199
200 return dummy.next;
201}
202
203// =============================================================================
204// 6. κ°μ₯ κ°κΉμ΄ Kκ° μ
205// =============================================================================
206
207vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
208 auto dist = [](const vector<int>& p) {
209 return p[0] * p[0] + p[1] * p[1];
210 };
211
212 auto cmp = [&dist](const vector<int>& a, const vector<int>& b) {
213 return dist(a) < dist(b);
214 };
215
216 priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> maxHeap(cmp);
217
218 for (auto& point : points) {
219 maxHeap.push(point);
220 if ((int)maxHeap.size() > k) {
221 maxHeap.pop();
222 }
223 }
224
225 vector<vector<int>> result;
226 while (!maxHeap.empty()) {
227 result.push_back(maxHeap.top());
228 maxHeap.pop();
229 }
230
231 return result;
232}
233
234// =============================================================================
235// 7. Top K λΉλ μμ
236// =============================================================================
237
238vector<int> topKFrequent(vector<int>& nums, int k) {
239 unordered_map<int, int> freq;
240 for (int num : nums) {
241 freq[num]++;
242 }
243
244 auto cmp = [&freq](int a, int b) { return freq[a] > freq[b]; };
245 priority_queue<int, vector<int>, decltype(cmp)> minHeap(cmp);
246
247 for (auto& [num, count] : freq) {
248 minHeap.push(num);
249 if ((int)minHeap.size() > k) {
250 minHeap.pop();
251 }
252 }
253
254 vector<int> result;
255 while (!minHeap.empty()) {
256 result.push_back(minHeap.top());
257 minHeap.pop();
258 }
259
260 return result;
261}
262
263// =============================================================================
264// ν
μ€νΈ
265// =============================================================================
266
267void printVector(const vector<int>& v) {
268 cout << "[";
269 for (size_t i = 0; i < v.size(); i++) {
270 cout << v[i];
271 if (i < v.size() - 1) cout << ", ";
272 }
273 cout << "]";
274}
275
276int main() {
277 cout << "============================================================" << endl;
278 cout << "ν μμ " << endl;
279 cout << "============================================================" << endl;
280
281 // 1. μ΅μ ν
282 cout << "\n[1] μ΅μ ν" << endl;
283 MinHeap minHeap;
284 minHeap.push(5);
285 minHeap.push(3);
286 minHeap.push(7);
287 minHeap.push(1);
288 cout << " μ½μ
: 5, 3, 7, 1" << endl;
289 cout << " μ΅μκ°: " << minHeap.top() << endl;
290 cout << " pop μμ: ";
291 while (!minHeap.empty()) {
292 cout << minHeap.pop() << " ";
293 }
294 cout << endl;
295
296 // 2. STL priority_queue
297 cout << "\n[2] STL priority_queue" << endl;
298 priority_queue<int> maxPQ; // μ΅λ ν
299 priority_queue<int, vector<int>, greater<int>> minPQ; // μ΅μ ν
300
301 for (int x : {3, 1, 4, 1, 5, 9}) {
302 maxPQ.push(x);
303 minPQ.push(x);
304 }
305
306 cout << " μ΅λ ν top: " << maxPQ.top() << endl;
307 cout << " μ΅μ ν top: " << minPQ.top() << endl;
308
309 // 3. ν μ λ ¬
310 cout << "\n[3] ν μ λ ¬" << endl;
311 vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
312 cout << " μ λ ¬ μ : ";
313 printVector(arr);
314 cout << endl;
315 heapSort(arr);
316 cout << " μ λ ¬ ν: ";
317 printVector(arr);
318 cout << endl;
319
320 // 4. Kλ²μ§Έ μμ
321 cout << "\n[4] Kλ²μ§Έ μμ" << endl;
322 vector<int> nums = {3, 2, 1, 5, 6, 4};
323 cout << " λ°°μ΄: [3,2,1,5,6,4]" << endl;
324 cout << " 2λ²μ§Έλ‘ ν° μμ: " << findKthLargest(nums, 2) << endl;
325 cout << " 3λ²μ§Έλ‘ μμ μμ: " << findKthSmallest(nums, 3) << endl;
326
327 // 5. μ€μκ° μ€νΈλ¦Ό
328 cout << "\n[5] μ€μκ° μ€νΈλ¦Ό" << endl;
329 MedianFinder mf;
330 mf.addNum(1);
331 mf.addNum(2);
332 cout << " [1, 2] μ€μκ°: " << mf.findMedian() << endl;
333 mf.addNum(3);
334 cout << " [1, 2, 3] μ€μκ°: " << mf.findMedian() << endl;
335
336 // 6. Top K λΉλ
337 cout << "\n[6] Top K λΉλ μμ" << endl;
338 vector<int> freqNums = {1, 1, 1, 2, 2, 3};
339 auto topK = topKFrequent(freqNums, 2);
340 cout << " [1,1,1,2,2,3], k=2: ";
341 printVector(topK);
342 cout << endl;
343
344 // 7. 볡μ‘λ μμ½
345 cout << "\n[7] 볡μ‘λ μμ½" << endl;
346 cout << " | μ°μ° | μκ°λ³΅μ‘λ |" << endl;
347 cout << " |--------------|------------|" << endl;
348 cout << " | μ½μ
| O(log n) |" << endl;
349 cout << " | μμ (top) | O(log n) |" << endl;
350 cout << " | μ΅μκ°/μ΅λκ°| O(1) |" << endl;
351 cout << " | ν κ΅¬μ± | O(n) |" << endl;
352 cout << " | ν μ λ ¬ | O(n log n) |" << endl;
353
354 cout << "\n============================================================" << endl;
355
356 return 0;
357}