Max Heap 구현 작성일 2018-07-15 | In algorithm Max Heap 구현 가능하면 가독성을 높여서 짜본 Heap이다. inline 함수를 최대한 활용해서 push와 pop 동작을 알기 쉽게 구현했다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354class Heap { int data[100001]; int bound; inline int LS(int a) { return 2*a; } inline int RS(int a) { return 2*a+1; } inline int PA(int a) { return a/2; } inline void swap(int x, int y) { int tmp = data[x]; data[x] = data[y]; data[y] = tmp; } inline int max(int x, int y){ return data[x] > data[y] ? x : y; } inline int max(int x, int y, int z) { return max(x, max(y, z)); } public: Heap() { memset(data, 0, sizeof(data)); bound = 1; } void push(int x) { int pos = bound; data[bound++] = x; while (data[pos] > data[PA(pos)] && pos > 1) { swap(pos, PA(pos)); pos = PA(pos); } } int pop() { if (bound == 1) return 0; int pos = 1; int ret = data[1]; data[1] = data[--bound]; data[bound] = -1; while(LS(pos) < bound || RS(pos) < bound) { int m = max(pos, LS(pos), RS(pos)); if (m != pos) { swap(m, pos); pos = m; } else break; } return ret; } };