---

코딩테스트에서 최솟값이나 최댓값을 반복해서 관리해야 하는 문제에서 자주 사용되는 자료구조가 Heap입니다.

단순히 가장 작은 값을 한 번 찾는 것이라면 min()을 사용할 수 있지만,

데이터를 계속 추가하면서 그때그때 가장 작은 값 또는 가장 큰 값을 꺼내야 한다.

와 같은 상황에서는 매번 전체 데이터를 탐색하는 것보다 Heap을 사용하는 것이 효율적입니다.

Python에서는 heapq 모듈을 이용해 Heap을 사용할 수 있습니다.

1. Heap이란?

Heap은 완전 이진 트리(Complete Binary Tree)를 기반으로 하는 자료구조입니다.

크게 두 종류가 있습니다.

Min Heap
→ 가장 작은 값이 Root에 위치

Max Heap
→ 가장 큰 값이 Root에 위치

최소 힙에서는

부모 ≤ 자식

최대 힙에서는

부모 ≥ 자식

관계가 유지됩니다.

예를 들어 최소 힙은 다음과 같은 형태를 가질 수 있습니다.

        1
      /   \
     3     2
    / \   /
   7   5  4

가장 작은 값인 1이 Root에 위치합니다.

여기서 Heap은 전체 데이터가 정렬된 자료구조는 아닙니다.

최소 힙이라면 부모가 자식보다 작거나 같다는 조건을 유지하면서 Root가 항상 최솟값이라는 점을 보장합니다.

완전 이진 트리와 List

완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 채워져 있고, 마지막 레벨은 왼쪽부터 차례대로 채워지는 구조입니다.

이러한 구조 덕분에 별도의 Node 객체 없이 List로 표현할 수 있습니다.

        1
      /   \
     3     2
    / \   /
   7   5  4

heap = [1, 3, 2, 7, 5, 4]

인덱스를 함께 보면

값        1   3   2   7   5   4
index     0   1   2   3   4   5

특정 위치 i를 기준으로 부모와 자식 위치를 계산할 수 있습니다.

부모
→ (i - 1) // 2

왼쪽 자식
→ 2 * i + 1

오른쪽 자식
→ 2 * i + 2

예를 들어 i = 1인 값 3의 자식은

왼쪽 자식
→ 2 * 1 + 1
→ index 3
→ 7

오른쪽 자식
→ 2 * 1 + 2
→ index 4
→ 5

가 됩니다.

Python의 heapq 역시 이런 방식으로 List를 Heap처럼 관리합니다.

실제로 사용할 때 이 공식을 직접 계산할 일은 거의 없고, heapq가 내부적으로 처리해 줍니다.

2. Heap은 왜 사용할까?

다음과 같은 List가 있다고 해봅시다.

arr = [8, 3, 5, 1, 9, 2]

일반적인 List에서 최솟값을 찾으면

min(arr)

전체 데이터를 확인해야 하기 때문에

O(N)

의 시간이 필요합니다.

반면 최소 힙에서는 가장 작은 값이 항상 Root에 존재합니다.

Python의 Heap은 List로 관리하므로

heap[0]

으로 최솟값을 바로 확인할 수 있습니다.

최솟값 확인
→ O(1)

또한 데이터를 추가하거나 제거한 뒤 Heap 구조를 다시 유지하는 과정은

O(log N)

으로 처리할 수 있습니다.

따라서 Heap은

최솟값이나 최댓값을 한 번 찾는 것이 아니라 계속 추가하고 꺼내야 하는 상황

에서 특히 유용합니다.

3. Python의 heapq

Python에서는 heapq 모듈을 이용해 Heap을 사용할 수 있습니다.

import heapq

heapq는 기본적으로 Min Heap으로 동작합니다.

heappush()

Heap에 데이터를 추가합니다.

import heapq

heap = []

heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)

print(heap)

Heap의 조건을 유지하면서 값이 추가됩니다.

시간복잡도
→ O(log N)

heappop()

가장 작은 값을 제거하면서 반환합니다.

print(heapq.heappop(heap))

1

다시 실행하면

print(heapq.heappop(heap))

2

처럼 작은 값부터 꺼낼 수 있습니다.

시간복잡도
→ O(log N)

heap[0]

최솟값을 제거하지 않고 확인만 하고 싶다면

heap[0]

을 사용합니다.

시간복잡도
→ O(1)

단,

heap[1]
heap[2]

가 두 번째, 세 번째로 작은 값이라는 의미는 아닙니다.

최소 힙에서 확실하게 보장되는 것은

heap[0]

이 최솟값이라는 점입니다.

heapify()

이미 존재하는 List를 Heap으로 바꿀 때 사용합니다.

import heapq

numbers = [5, 3, 8, 1, 2]

heapq.heapify(numbers)

print(numbers)

heapify()는 새로운 List를 반환하는 것이 아니라 기존 List 자체를 Heap으로 변경합니다.

heapq.heappop(numbers)

이후 바로 Heap처럼 사용할 수 있습니다.

시간복잡도
→ O(N)

주요 메서드 정리

기능	Python	시간복잡도
데이터 추가	heappush()	O(log N)
최솟값 삭제 / 반환	heappop()	O(log N)
최솟값 확인	heap[0]	O(1)
List → Heap	heapify()	O(N)

코딩테스트에서는 우선 이 네 가지를 기억해두면 됩니다.

4. Max Heap

Python의 heapq는 기본적으로 Min Heap입니다.

코딩테스트에서 Max Heap이 필요하다면 주로 값에 -를 붙이는 방법을 사용합니다.

예를 들어

5
2
8
1

을

-5
-2
-8
-1

로 저장합니다.

Min Heap 입장에서는 -8이 가장 작은 값이기 때문에 가장 먼저 나오게 됩니다.

꺼낸 뒤 다시 -를 붙이면

-(-8)
→ 8

원래의 최댓값을 얻을 수 있습니다.

import heapq

heap = []

heapq.heappush(heap, -5)
heapq.heappush(heap, -2)
heapq.heappush(heap, -8)
heapq.heappush(heap, -1)

max_value = -heapq.heappop(heap)

print(max_value)

8

따라서 Max Heap은 다음 형태로 기억할 수 있습니다.

# 넣을 때
heapq.heappush(heap, -value)

# 꺼낼 때
value = -heapq.heappop(heap)

5. Priority Queue

Heap과 함께 자주 등장하는 개념이 Priority Queue(우선순위 큐)입니다.

일반적인 Queue는 FIFO 구조입니다.

First In First Out

먼저 들어온 데이터
→ 먼저 나감

예를 들어

A → B → C

순서로 들어오면

A → B → C

순서로 나옵니다.

반면 Priority Queue는 들어온 순서보다 우선순위를 기준으로 데이터를 꺼냅니다.

예를 들어

작업        우선순위

A              3
B              1
C              2

이고 숫자가 작을수록 우선순위가 높다면

B → C → A

순서로 처리됩니다.

Heap과 Priority Queue의 관계

Heap과 Priority Queue는 같은 개념은 아닙니다.

Priority Queue
→ 우선순위가 높은 데이터를 먼저 꺼내는 방식

Heap
→ Priority Queue를 효율적으로 구현할 때 자주 사용하는 자료구조

Heap을 이용하면 데이터의 삽입과 삭제를

O(log N)

으로 처리할 수 있기 때문에 Priority Queue 구현에 자주 사용됩니다.

Tuple을 이용한 우선순위 관리

Python의 Heap에는 Tuple도 넣을 수 있습니다.

import heapq

heap = []

heapq.heappush(heap, (2, "Task B"))
heapq.heappush(heap, (1, "Task A"))
heapq.heappush(heap, (3, "Task C"))

Tuple은 앞의 값부터 비교하기 때문에

heapq.heappop(heap)

결과는

(1, 'Task A')

가 됩니다.

따라서

(priority, data)

형태로 저장하면 Priority Queue처럼 사용할 수 있습니다.

heapq.heappush(heap, (priority, value))

코딩테스트에서는 다음과 같은 형태도 자주 볼 수 있습니다.

heapq.heappush(heap, (distance, node))

예를 들어 다익스트라 알고리즘에서는 현재까지의 거리를 우선순위로 사용하여 거리가 짧은 Node부터 처리할 수 있습니다.

6. Queue와 Priority Queue 비교

자료구조	데이터를 꺼내는 기준
Queue	먼저 들어온 데이터
Priority Queue	우선순위가 높은 데이터

즉 문제에서

먼저 들어온 순서대로 처리한다.

라면 Queue를,

가장 작은 값이나 우선순위가 높은 값부터 계속 처리한다.

라면 Priority Queue와 Heap을 생각해볼 수 있습니다.

7. 코딩테스트에서 언제 사용할까?

Heap은 특히 다음과 같은 상황에서 생각해볼 수 있습니다.

최솟값을 반복해서 꺼낼 때

현재 데이터 중 가장 작은 값을 꺼낸다.
새로운 데이터를 추가한다.
다시 가장 작은 값을 꺼낸다.

heapq.heappush(heap, value)

min_value = heapq.heappop(heap)

최댓값을 반복해서 꺼낼 때

heapq.heappush(heap, -value)

max_value = -heapq.heappop(heap)

우선순위가 높은 작업부터 처리할 때

heapq.heappush(heap, (priority, task))

상위 K개의 값을 관리할 때

전체 데이터를 매번 정렬하는 대신 일정 크기의 Heap만 유지하는 방식으로 사용할 수 있습니다.

예를 들어 가장 큰 3개의 값만 유지한다면

if len(heap) < 3:
    heapq.heappush(heap, value)
else:
    ...

와 같은 방식으로 접근할 수 있습니다.

최단 거리 문제

다익스트라 알고리즘에서는

heapq.heappush(heap, (distance, node))

형태로 사용하여 현재까지 거리가 가장 짧은 Node부터 처리할 수 있습니다.

가장 작은 값들을 반복해서 합칠 때

문제에서

가장 작은 두 값을 꺼낸다.
두 값을 합친다.
합친 값을 다시 넣는다.

과 같은 과정이 반복된다면 Heap을 생각해볼 수 있습니다.

a = heapq.heappop(heap)
b = heapq.heappop(heap)

heapq.heappush(heap, a + b)

8. 한눈에 정리

Min Heap

import heapq

heap = []

heapq.heappush(heap, value)

value = heapq.heappop(heap)

minimum = heap[0]

List → Heap

arr = [5, 3, 1, 7, 2]

heapq.heapify(arr)

Max Heap

heapq.heappush(heap, -value)

maximum = -heapq.heappop(heap)

Priority Queue

heapq.heappush(heap, (priority, value))

priority, value = heapq.heappop(heap)

시간복잡도

최솟값 확인
→ O(1)

heappush
→ O(log N)

heappop
→ O(log N)

heapify
→ O(N)

마무리

Heap은

최솟값이나 최댓값을 효율적으로 관리하기 위한 자료구조

라고 생각하면 됩니다.

특히 코딩테스트에서

최솟값 / 최댓값을 계속 꺼낸다.

데이터를 추가하면서
최솟값 / 최댓값을 계속 관리한다.

우선순위가 높은 데이터를 먼저 처리한다.

와 같은 상황이 나온다면 Heap을 떠올려볼 수 있습니다.

Queue
→ 먼저 들어온 데이터부터 처리

Priority Queue
→ 우선순위가 높은 데이터부터 처리

Heap
→ Priority Queue를 효율적으로 구현할 때 자주 사용하는 자료구조

Python에서는 heapq를 이용해 Min Heap을 사용할 수 있고, 코딩테스트에서는 우선

heapq.heappush()
heapq.heappop()
heapq.heapify()
heap[0]

정도를 익혀두면 좋습니다.

결국 Heap 문제에서는 메서드 자체를 외우는 것보다

"최솟값이나 최댓값을 반복해서 관리해야 하는가?"

를 문제에서 발견하는 것이 가장 중요합니다.