자료구조 — 힙(Heap) 개념 정리

---

1. 힙이란?

힙(Heap) 은 여러 데이터 중에서 가장 작은 값 또는 가장 큰 값을 빠르게 찾고 꺼내기 위한 자료구조이다.

예를 들어 다음과 같은 숫자가 있다고 생각해보자.

5, 2, 8, 1, 3

여기서 계속해서 가장 작은 값을 꺼내야 하는 상황이 있다면 힙을 사용할 수 있다.

5, 2, 8, 1, 3
        ↓
    가장 작은 값
        ↓
        1

힙의 핵심은 다음과 같다.

최솟값 또는 최댓값을 빠르게 꺼낼 수 있다.

---

2. 힙은 우선순위 큐와 연결된다

앞에서 배운 일반적인 큐는 먼저 들어온 데이터가 먼저 나가는 FIFO 구조였다.

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

하지만 항상 먼저 들어온 데이터를 처리해야 하는 것은 아니다.

예를 들어 병원에서 환자를 처리한다고 생각해보자.

A 환자 → 일반
B 환자 → 응급
C 환자 → 일반

단순히 들어온 순서대로 처리하는 것이 아니라 우선순위가 높은 환자를 먼저 처리해야 하는 상황이 있을 수 있다.

이처럼 데이터가 들어온 순서가 아니라 우선순위에 따라 데이터를 꺼내는 구조를 우선순위 큐(Priority Queue) 라고 한다.

Queue
→ 들어온 순서가 중요

Priority Queue
→ 우선순위가 중요

그리고 힙은 우선순위 큐를 구현할 때 대표적으로 사용하는 자료구조이다.

---

3. 최소 힙과 최대 힙

힙은 크게 두 가지 형태로 생각할 수 있다.

최소 힙(Min Heap)

가장 작은 값이 우선순위를 가진다.

        1
       / \
      3   2
     / \
    7   5

부모 노드는 자식 노드보다 작거나 같다.

부모 ≤ 자식

따라서 가장 위에는 항상 가장 작은 값이 위치한다.

최소 힙
→ 최솟값을 빠르게 확인하고 제거

---

최대 힙(Max Heap)

가장 큰 값이 우선순위를 가진다.

        9
       / \
      7   8
     / \
    3   5

부모 노드는 자식 노드보다 크거나 같다.

부모 ≥ 자식

따라서 가장 위에는 가장 큰 값이 위치한다.

최대 힙
→ 최댓값을 빠르게 확인하고 제거

---

4. Python에서는 heapq를 사용한다

Python에서는 힙을 사용할 때 heapq 모듈을 사용한다.

import heapq

Python의 heapq는 기본적으로 최소 힙(Min Heap) 으로 동작한다.

먼저 빈 리스트를 만든다.

heap = []

데이터를 넣을 때는 heappush()를 사용한다.

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

가장 작은 값을 꺼낼 때는 heappop()을 사용한다.

value = heapq.heappop(heap)

print(value)

결과는

1

이다.

즉,

heappush()
→ 데이터 삽입

heappop()
→ 가장 작은 데이터 제거

로 기억하면 된다.

---

5. 힙에서 가장 작은 값 확인하기

최소 힙에서는 가장 작은 값이 항상 맨 앞에 위치한다.

따라서

heap[0]

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

import heapq

heap = []

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

print(heap[0])

결과는

2

이다.

이때 heap[0]은 데이터를 제거하지 않는다.

heap[0]
→ 최솟값 확인

heappop()
→ 최솟값 확인 + 제거

---

6. 힙은 정렬된 리스트가 아니다

여기서 주의해야 할 점이 있다.

힙에 데이터를 넣었다고 해서 리스트 전체가 완전히 정렬되는 것은 아니다.

예를 들어

import heapq

heap = []

for num in [5, 2, 8, 1, 3]:
    heapq.heappush(heap, num)

print(heap)

출력된 리스트가 전체적으로 완벽하게 정렬되어 있다고 생각하면 안 된다.

힙에서 중요한 것은

모든 데이터가 정렬되어 있음

이 아니라

최소 힙
→ 가장 작은 값이 heap[0]에 있음

이라는 것이다.

즉,

힙은 전체 데이터를 정렬하기 위한 구조가 아니라 우선순위가 가장 높은 데이터를 빠르게 찾기 위한 구조이다.

---

7. 힙의 시간복잡도

힙에서 중요한 연산은 삽입과 삭제이다.

삽입 → O(log N)
삭제 → O(log N)

최소 힙에서 최솟값을 확인하는 것은

heap[0]
→ O(1)

이다.

정리하면

연산	시간복잡도
최솟값 확인	O(1)
삽입	O(log N)
최솟값 제거	O(log N)

왜 삽입과 삭제가 O(log N)인지는 나중에 트리(Tree) 를 배우면 더 자연스럽게 이해할 수 있다.

현재는

힙의 삽입/삭제
→ O(log N)

정도로 기억해두면 된다.

---

8. 왜 그냥 min()을 사용하지 않을까?

리스트에서도 min()을 이용하면 가장 작은 값을 찾을 수 있다.

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

print(min(numbers))

하지만 min()은 리스트를 확인하면서 최솟값을 찾아야 한다.

min()
→ O(N)

반면 최소 힙에서는

heap[0]
→ O(1)

로 최솟값을 확인할 수 있다.

특히 데이터를 계속 추가하면서 최솟값을 반복해서 꺼내야 하는 상황에서는 힙이 유용하다.

데이터 추가
↓
최솟값 제거
↓
데이터 추가
↓
최솟값 제거
↓
반복

이런 상황에서 힙의 장점이 커진다.

---

9. 최대 힙은 어떻게 사용할까?

Python의 heapq는 기본적으로 최소 힙이다.

최대 힙이 필요한 경우에는 여러 방법이 있지만, 코딩 테스트에서는 값의 부호를 바꾸는 방법을 자주 사용한다.

import heapq

heap = []

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

value = -heapq.heappop(heap)

print(value)

결과는

8

이다.

원래 값에 -를 붙여 저장하면

8 → -8
5 → -5
2 → -2

가 된다.

최소 힙은 가장 작은 값인 -8을 먼저 꺼낸다.

다시 부호를 바꾸면

-(-8)
→ 8

이므로 원래 값 중 가장 큰 값을 얻을 수 있다.

최대 힙

값에 -를 붙여 저장
↓
heappop()
↓
다시 -를 붙임
↓
최댓값

---

10. 앞에서 배운 자료구조와 연결하기

지금까지 배운 자료구조를 비교해보자.

Stack

마지막에 들어온 데이터
↓
먼저 처리
↓
LIFO
↓
DFS

Queue

먼저 들어온 데이터
↓
먼저 처리
↓
FIFO
↓
BFS

Hash

Key를 이용
↓
빠른 검색
↓
dict / set

Heap

우선순위가 높은 데이터
↓
먼저 처리
↓
Priority Queue

즉, Stack과 Queue와 Heap의 차이를 "어떤 데이터를 먼저 처리할 것인가?"라는 관점에서 볼 수 있다.

Stack
→ 가장 최근 데이터

Queue
→ 가장 오래된 데이터

Heap
→ 가장 우선순위가 높은 데이터

---

11. Queue와 Heap의 차이

Queue와 Heap은 특히 비교해서 기억하면 좋다.

구분	Queue	Heap
처리 기준	들어온 순서	우선순위
먼저 처리	먼저 들어온 데이터	우선순위가 높은 데이터
Python	deque	heapq
대표 연산	append(), popleft()	heappush(), heappop()
관련 개념	BFS	Priority Queue

일반 큐에서는

A → B → C

처리 순서
A → B → C

이다.

하지만 우선순위가

A → 우선순위 3
B → 우선순위 1
C → 우선순위 2

라면 최소 힙을 이용한 우선순위 큐에서는

B → C → A

순서로 처리할 수 있다.

---

12. Heap과 Tree의 관계

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

        1
       / \
      3   2
     / \
    7   5

하지만 Python에서는 직접 노드를 만들어 연결할 필요가 없다.

heapq는 리스트를 이용해서 힙을 관리한다.

heap = []

따라서 지금 단계에서는

Heap
↓
Tree 형태를 기반으로 함
↓
Python에서는 list + heapq 사용

정도로 이해하면 충분하다.

완전 이진 트리가 무엇인지, 왜 O(log N)인지는 다음에 트리를 공부하면서 다시 연결하면 된다.

---

13. Heap과 다익스트라의 관계

힙은 나중에 그래프 알고리즘인 다익스트라(Dijkstra) 를 배울 때 다시 등장한다.

다익스트라는 여러 후보 중에서

현재 가장 거리가 짧은 노드

를 계속 선택해야 한다.

즉,

여러 후보
↓
가장 작은 값 선택
↓
처리
↓
다시 가장 작은 값 선택

과 같은 과정이 필요하다.

이때 최소 힙을 이용한 우선순위 큐를 사용할 수 있다.

Heap
↓
Priority Queue
↓
가장 작은 값 빠르게 선택
↓
Dijkstra

현재는 다익스트라를 몰라도 괜찮다.

나중에 그래프를 공부하면서

"힙을 여기서 사용하는구나."

라고 다시 연결하면 된다.

---

핵심 정리

Heap
=
우선순위가 높은 데이터를
빠르게 꺼내기 위한 자료구조

Python

import heapq

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

최소 힙

가장 작은 값
→ 먼저 나감

최대 힙

가장 큰 값
→ 먼저 나감

시간복잡도

최솟값 확인 → O(1)
삽입        → O(log N)
삭제        → O(log N)

주요 연관 개념

Heap
├── Priority Queue
├── Tree
└── Dijkstra

---

지금까지 배운 자료구조 비교

구분	Stack	Queue	Hash	Heap
핵심	LIFO	FIFO	빠른 탐색	우선순위
Python	list	deque	dict, set	heapq
먼저 처리	마지막 데이터	먼저 들어온 데이터	Key로 찾은 데이터	우선순위 높은 데이터
주요 활용	DFS	BFS	검색, 중복 검사	Priority Queue
이후 연결	DFS	BFS	방문 처리	Tree, Dijkstra

---

자료구조 연결

Stack
│
└── LIFO
    └── DFS

Queue
│
└── FIFO
    └── BFS

Hash
│
├── dict
│   └── Key : Value
│
└── set
    └── 중복 / 존재 여부

Heap
│
├── Priority Queue
├── Tree
└── Dijkstra

지금까지 배운 내용을 하나의 질문으로 구분해보면 다음과 같다.

Stack
→ 가장 최근 데이터는 무엇인가?

Queue
→ 가장 먼저 들어온 데이터는 무엇인가?

Hash
→ 이 데이터가 존재하는가?

Heap
→ 지금 가장 우선순위가 높은 데이터는 무엇인가?

---

한 줄 요약

힙은 최솟값이나 최댓값처럼 우선순위가 높은 데이터를 빠르게 꺼내기 위한 자료구조이며, Python에서는 heapq를 사용한다.