최소힙(Min Heap) 구현
Joonas' Note
최소힙(Min Heap) 구현 본문
이진 트리 중에서도 힙.
힙 중에서도 최소힙을 구현한 코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//////////////////////////////////////////// | |
// @title Implement of Min-Heap | |
// @author Joonas <joonas.yoon@gmail.com> | |
// @blog https://joonas.tistory.com | |
//////////////////////////////////////////// | |
#define MAX_SIZE 100001 | |
template <typename T> | |
class MinHeap { | |
private: | |
int sz; | |
T a[MAX_SIZE]; | |
public: | |
MinHeap() { | |
sz = 0; | |
} | |
bool empty() { | |
return sz == 0; | |
} | |
void clear() { | |
sz = 0; | |
} | |
T top() { // or peek() | |
return a[0]; | |
} | |
void pop() { | |
a[0] = a[--sz]; | |
heapify(0); | |
} | |
void push(T data) { | |
a[sz] = data; | |
for (int i = sz++; i;) { | |
int p = (i - 1) >> 1; | |
if (a[p] < a[i]) break; | |
swap(a[p], a[i]); | |
i = p; | |
} | |
} | |
private: | |
void heapify(int p) { | |
int l = 2 * p + 1; | |
int r = l + 1; | |
int k = p; | |
if (l < sz && a[l] < a[k]) k = l; | |
if (r < sz && a[r] < a[k]) k = r; | |
if (k != p) { | |
swap(a[k], a[p]); | |
heapify(k); | |
} | |
} | |
}; |
C++에서 대소비교에 기본값인 less than(<) 연산만 사용하여 구현했기 때문에, < 연산자만 오버로딩한다면, 다른 구조체/클래스도 무난하게 동작한다.
'알고리즘 > 자료구조' 카테고리의 다른 글
[C++ STL] vector 구현하기 (0) | 2020.03.19 |
---|---|
비재귀 세그먼트 트리 - Efficient and easy segment tree (2) | 2019.12.02 |
C++로 작성한 레드블랙트리 (2) | 2017.11.02 |