https://www.acmicpc.net/problem/11279
백준저지 11279번 최대 힙 문제입니다.
파이썬이나 C++ STL에서 제공해주는 heap, priority_queue 자료구조를 사용하면 간단하게 풀 수 있지만, 최대힙을 직접 구현하면서 해당 자료구조에 대하여 한번 공부해도록 하겠습니다.
힙이라는 자료구조는 일단 ADT(Abstract Data Type)이기 때문에 직접적으로 메모리상에 어떠한 구조로 나열되든간에, 설계된 대로만 동작하면 맞습니다.
Complete Binary Tree라는 자료구조 특성상 일반 트리 처럼 포인터로 구현을 하기 보다는 배열로 구현하는 것이 편합니다.
저도 이번에 배열로 구현을 할 예정이며 C++ STL에서 제공하는 vector 컨테이너를 사용하겠습니다.
배열로 구현한 Binary Tree는 각 노드 번호 i에 대하여 Left child는 i*2, Right child는 i*2+1의 번호를 갖습니다. 그러기 위해서는 루트노드의 번호를 1부터 새야 하므로 data[0]에는 더미노드를 하나 넣어서 1부터 새도록 구현했습니다.
최대 힙은 두개의 연산을 제공하는데, 새로운 데이터를 넣는 연산과, 힙에서 최대값을 빼내는 연산입니다.
최대 힙의 구조상 부모 노드는 항상 자식 노드보다 값이 크므로, 힙에서 값을 빼내는 연산은 항상 루트 노드의 값을 빼내게 됩니다.
각각의 연산을 push와 pop이라고 명명하겠습니다.
push 연산은 다음과 같은 절차로 이루어집니다.
1. Complete binary tree가 되도록, 마지막 위치에 넣는 값을 집어넣습니다.
2. 직속 부모 노드와 값을 비교하여 자신의 값이 직속 부모 노드 보다 값이 작을 때 까지 부모 노드와 위치를 바꿉니다.
pop 연산은 다음과 같은 절차로 이루어집니다.
1. 리턴할 루트 노드의 값을 따로 빼놓습니다. 그리고 가장 마지막 노드의 값을 루트 노드의 위치로 이동시킵니다.
2. 이동된 노드가 자신의 양쪽 자식 노드와 비교해서 둘 중에 자신보다 큰 값을 가진 노드가 있다면 그 중 가장 큰 노드를 자신의 위치와 바꿉니다. 자신이 모든 직속 자식들보다 값이 클 때 까지 반복합니다.
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define MAX_SIZE 100001
class max_heap {
private:
vector<int> data;
public:
max_heap() {
this->data.push_back(-1); // index 0 means dummy data
}
max_heap(int size) {
this->data.reserve(size);
this->data.push_back(-1); //index 0 is dummy data
}
int pop() {
if (this->data.size() <= 1) {
//heap is empty
return 0;
}
int current = 1;
int left_child = 2;
int right_child = 3;
int ret = this->data[current];
int last = this->data.size() - 1;
swap(this->data[current], this->data[last]);
this->data.pop_back();
while (this->data.size() > left_child) { //when left child exist
int larger_index = left_child;
if (this->data.size() > right_child) { //when right child exist
if (this->data[right_child] > this->data[left_child]) {
larger_index = right_child;
}
}
if (this->data[larger_index] > this->data[current]) {
swap(this->data[current], this->data[larger_index]);
current = larger_index;
left_child = current * 2;
right_child = left_child + 1;
} else {
break;
}
}
return ret;
}
bool push(int val) {
this->data.push_back(val);
int current = data.size() - 1;
int parent = current/2;
while (parent > 0 && this->data[current] > this->data[parent]) {
swap(this->data[current], this->data[parent]);
current = parent;
parent = current/2;
}
}
};
int main() {
max_heap heap(MAX_SIZE);
int n;
cin >> n;
for (int i=0; i < n; i++) {
int tmp;
cin >> tmp;
if (tmp > 0) {
heap.push(tmp);
} else {
cout << heap.pop() << endl;
}
}
return 0;
}
