문제
자연수 x가 주어지면 힙에 삽입하고, 0이 주어지면 힙에서 가장 큰 값을 출력하고 제거한다. 힙이 비어있을 때 0이 주어지면 0을 출력한다.
핵심 포인트
- 배열 기반 힙: 인덱스 1부터 시작. 부모
i/2, 왼쪽 자식i*2, 오른쪽 자식i*2+1. - Push (Sift Up): 마지막에 삽입 후 부모와 비교하며 위로 올린다.
- Pop (Sift Down): 루트를 제거하고 마지막 원소를 루트에 놓은 뒤, 자식과 비교하며 아래로 내린다.
C++ 풀이
#include <iostream>
using namespace std;
int heap[100001];
int heap_size = 0;
void push(int data) {
int pos = ++heap_size;
// Sift Up: 부모보다 크면 교환하며 올라감
while (pos != 1 && data > heap[pos / 2]) {
heap[pos] = heap[pos / 2];
pos /= 2;
}
heap[pos] = data;
}
int pop() {
if (heap_size == 0) return 0;
int result = heap[1]; // 루트(최대값) 저장
heap[1] = heap[heap_size--]; // 마지막 원소를 루트로
// Sift Down: 자식 중 큰 값과 교환하며 내려감
int parent = 1;
int child = 2;
while (child <= heap_size) {
// 오른쪽 자식이 더 크면 오른쪽 선택
if (child + 1 <= heap_size && heap[child] < heap[child + 1])
child++;
// 부모가 자식보다 크거나 같으면 종료
if (heap[parent] >= heap[child]) break;
// 교환
int tmp = heap[parent];
heap[parent] = heap[child];
heap[child] = tmp;
parent = child;
child = parent * 2;
}
return result;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N, x;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> x;
if (x == 0) cout << pop() << '\n';
else push(x);
}
return 0;
}
Push 동작 (Sift Up)
삽입 전: 삽입 후 (10 삽입): Sift Up 완료:
8 8 10
/ \ / \ / \
5 3 5 3 8 3
/ /
10 5
새 원소를 마지막 위치에 놓고, 부모와 비교하면서 더 크면 자리를 바꾸며 올라간다. 루트에 도달하거나 부모가 더 크면 멈춘다.
Pop 동작 (Sift Down)
Pop 전: 루트 제거 + 마지막 이동: Sift Down 완료:
10 3 8
/ \ / \ / \
8 3 8 (빈) 5 3
/ /
5 5
루트를 반환하고, 마지막 원소를 루트에 놓은 뒤, 자식 중 큰 것과 비교하며 내려간다.
STL 대안
실전에서는 priority_queue를 쓰면 된다. 이 문제의 의의는 힙의 내부 구조를 직접 구현하며 이해하는 것이다.
#include <queue>
priority_queue<int> pq; // 기본이 최대 힙
pq.push(x);
pq.top(); // 최대값 조회
pq.pop(); // 최대값 제거
복잡도
- Push: O(log N) — 트리 높이만큼 올라감
- Pop: O(log N) — 트리 높이만큼 내려감
- 전체: O(N log N)
힙은 “부모가 항상 자식보다 크다(또는 작다)”는 단순한 규칙 하나로 O(log N) 삽입/삭제를 보장하는 자료구조다.
댓글