Heap

왜 배우는가: 힙은 최댓값·최솟값을 로그 시간에 꺼내는 우선순위 큐의 기본 구현이며, 작업 스케줄링·최단경로·정렬 등 실무 알고리즘 전반에 쓰인다. 시험에서는 1교시 용어 문제와 3교시 비교 논술로 반복 출제된다.

출제 이력: 제124회 3교시 2번, 제90회 1교시 10번

1. 한 줄 정의와 핵심 키워드

힙(Heap)은 완전이진트리 형태로 부모와 자식 노드 사이에 키 값의 대소 관계(힙 속성)를 유지하는 자료구조이며, 최댓값 또는 최솟값을 빠르게 꺼낸다.

핵심 키워드

• 완전이진트리(Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 채워지고, 마지막 레벨은 왼쪽부터 채워진다.
• 힙 속성(Heap Property): 부모와 자식 사이의 키 값 대소 관계.
• 최대 힙(Max-heap): 부모 키 ≥ 자식 키, 루트에 최댓값이 있다.
• 최소 힙(Min-heap): 부모 키 ≤ 자식 키, 루트에 최솟값이 있다.
• 우선순위 큐(Priority Queue): 힙으로 구현하는 대표적 추상 자료형.
• 배열 표현: 인덱스를 1부터 쓰면 부모 i/2, 왼쪽 자식 2i, 오른쪽 자식 2i+1이다.
• 힙 정렬(Heap Sort): 힙을 이용한 비교 기반 정렬.

2. 개념 풀이

쉽게 말하면 힙은 '가장 중요한 값이 맨 위에 올라와 있는 트리'다. 값이 큰 것이 위에 있으면 최대 힙, 작은 것이 위에 있으면 최소 힙이다. 여러 값 중 최댓값이나 최솟값만 빨리 찾으면 되는 상황에 맞춘 구조다.

정식 정의는 다음과 같다. 힙은 완전이진트리(Complete Binary Tree)를 기본 형태로 하며, 각 노드의 키가 자식 노드의 키와 대소 관계를 이루는 힙 속성(Heap Property)을 만족하는 트리 기반 자료구조다. 형제 노드 사이에는 대소 관계가 정해지지 않는다는 점이 중요하다.

힙은 두 가지 조건을 동시에 만족한다. 첫째는 모양 속성으로, 완전이진트리여야 한다. 둘째는 힙 속성으로, 모든 부모-자식 쌍에서 키 값의 대소가 일관되어야 한다. 이 두 조건 덕분에 트리의 높이는 완전이진트리의 형태에 따라 정해진다.

힙은 크게 두 유형으로 나뉜다. 최대 힙(Max-heap)은 부모 키 값이 자식 키 값보다 크거나 같고, 루트에 전체 최댓값이 온다. 최소 힙(Min-heap)은 부모 키 값이 자식 키 값보다 작거나 같고, 루트에 전체 최솟값이 온다. 두 유형은 대소 방향만 다르고 구조와 연산 원리는 같다.

힙은 보통 배열로 저장한다. 인덱스를 1부터 쓰면 계산이 간단하다. 부모 인덱스는 자식 인덱스를 2로 나눈 몫이고, 왼쪽 자식은 부모의 2배, 오른쪽 자식은 부모의 2배에 1을 더한 위치다. 노드를 따로 포인터로 연결하지 않아도 되므로 메모리 효율이 좋다.

3. 등장 배경과 필요성

여러 데이터 중 최댓값이나 최솟값을 반복해서 꺼내야 하는 문제가 많다. 정렬된 배열은 삽입이 느리고, 일반 배열은 최댓값 탐색에 매번 전체를 훑어야 한다. 이 문제를 해결하려고 최댓값·최솟값을 빠르게 얻으면서도 삽입과 삭제를 로그 시간에 처리하는 구조가 필요해졌다.

힙은 1964년 J. W. J. Williams가 힙 정렬을 위한 자료구조로 도입했다. 이후 우선순위 큐를 구현하는 가장 일반적인 방법으로 자리 잡았다. 이진 힙은 정렬 알고리즘과 우선순위 큐 양쪽에 쓰이는 이유다.