힙(Heap)

힙(Heap)이란 무엇인가

힙은 완전 이진 트리 기반의 자료구조로, 항상 특정 규칙을 만족하도록 값이 정렬되어 있다. 이 규칙 덕분에 힙은 최댓값이나 최솟값을 매우 빠르게 찾는 데 특화된 구조다. 힙은 정렬된 자료구조는 아니지만, “가장 크다” 혹은 “가장 작다”라는 기준 하나만큼은 항상 보장한다는 점이 핵심이다.

힙에는 크게 두 가지가 있다. 최대 힙(Max Heap)은 부모 노드가 항상 자식 노드보다 크거나 같고, 최소 힙(Min Heap)은 부모 노드가 항상 자식 노드보다 작거나 같다. 어떤 힙을 쓰느냐에 따라 루트 노드에는 항상 최댓값 또는 최솟값이 위치한다.

힙과 트리의 관계

힙은 아무 이진 트리가 아니라 완전 이진 트리 형태를 유지해야 한다. 즉, 노드는 항상 아래 레벨의 왼쪽부터 차례대로 채워진다. 이 조건 덕분에 힙은 트리 구조이면서도 배열로 효율적으로 표현할 수 있다.

완전 이진 트리의 성질을 그대로 사용하기 때문에, 배열에서 다음 규칙이 성립한다.

• 인덱스 i의 왼쪽 자식 → i * 2

• 인덱스 i의 오른쪽 자식 → i * 2 + 1

• 인덱스 i의 부모 → i // 2

이 구조 덕분에 힙은 포인터 없이도 트리를 다룰 수 있다.

# 최대 힙을 배열로 표현한 예시 (0번 인덱스는 사용하지 않음)
heap = [None, 10, 7, 8, 3, 5]

위 배열에서 10은 항상 최댓값이며, 배열의 맨 앞(루트)에 위치한다.

힙에서의 삽입과 삭제

힙의 가장 중요한 연산은 삽입과 삭제(보통 루트 삭제)다.

새로운 값을 힙에 삽입할 때는, 우선 트리의 가장 마지막 위치(배열의 끝)에 값을 넣는다. 이후 힙의 규칙을 깨지 않도록 부모 노드와 비교하면서 위로 올라간다. 이 과정을 heapify up이라고 한다.

반대로 값을 삭제할 때는, 보통 루트 노드를 제거한다. 루트 자리에 마지막 노드를 올린 뒤, 자식 노드들과 비교하며 아래로 내려보낸다. 이 과정을 heapify down이라고 한다.

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)

print(heapq.heappop(heap))  # 2 (최솟값)

파이썬의 heapq는 최소 힙을 기본으로 제공하며, 최댓값 힙은 값에 -를 붙이는 방식으로 구현한다.

힙의 시간 복잡도

힙의 높이는 완전 이진 트리이기 때문에 O(log N) 수준이다. 따라서 삽입과 삭제 모두 최악의 경우에도 트리의 높이만큼만 이동하면 되며, 시간 복잡도는 다음과 같다.

• 삽입: O(log N)

• 삭제(최댓값/최솟값 제거): O(log N)

• 최댓값/최솟값 조회: O(1)

특히 루트에 항상 최댓값이나 최솟값이 있기 때문에, 값을 “찾는” 비용은 거의 들지 않는다는 점이 힙의 가장 큰 장점이다.

힙은 언제 사용할까

힙은 전체를 정렬할 필요는 없지만, 항상 가장 중요한 값 하나를 빠르게 꺼내야 하는 상황에서 사용된다. 예를 들어 우선순위 큐, 작업 스케줄링, 다익스트라 알고리즘, 힙 정렬 등이 대표적인 활용 사례다.

정리하면 힙은 완전 이진 트리 기반의 자료구조이고 최댓값 또는 최솟값을 빠르게 다루기 위해 설계되었으며 삽입과 삭제는 O(log N), 조회는 O(1)로 동작한다.