힙(Heap)이란 무엇인가?
- 힙은 완전 이진 트리의 형태를 가진 자료구조.
- 최댓값과 최솟값을 빠르게 찾는데 유용하며, 부모-자식 간 정렬은 보장하고, 형제간의 정렬은 보장하지않기 때문에 반정렬 상태(느슨한 정렬 상태)이다
- 이진 탐색 트리(BST)와 다르게 중복값이 허용된다.
- 트리구조를 가지고 있기 때문에 삽입/삭제 시간 복잡도는 O(logn)이다.
- 힙 자료구조는 보통 배열을 사용하며 0번째 인덱스는 계산을 편하게 하기 위새 사용하지 않는다. 즉, 루트노드의 인덱스가 1이다.
- 부모 자식간의 인덱스 관계는 부모 인덱스가 N일 때, 왼쪽 자식은 2N 오른쪽 자식은 2N+1을 가진다.
- 완전 이진트리이기 때문에 노드마다 포인터를 따로 저장하지 않아도 배열의 인덱스만으로 부모와 자식의 위치를 찾아아낼 수 있다.
힙 (Heap) vs 이진 탐색 트리 (Binary Search Tree)
| 힙 | 이진 탐색 트리 | |
| 트리 형태 | 완전 이진 트리 | 이진 트리 |
| 원소의 중복 여부 | 중복 가능 | 중복 불가능 |
| 원소의 정렬 여부 | 정렬 X | 정렬 O (왼쪽자식 < 부모 < 오른쪽 자식) |
| 원소 탐색 시간 복잡도 | O(n) (순차 탐색) | O(logn) (이진 탐색) |
| 원소의 삽입 및 삭제 시간 복잡도 | O(logn) | O(logn) / O(n) (편항트리) |
| 최댓값/최솟값 참조 시간 복잡도 | O(1) | O(logn) / O(n) (편향트리) |
최대 힙 (Max Heap)과 최소 힙 (Min Heap)
최대 힙 (Max Heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
- 루트노드에 항상 가장 큰 값이 존재
- key(부모 노드) >= key(자식 노드)
최소 힙(Min Heap)
- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
- 루트노드에 항상 가장 작은 값이 존재
- key(부모 노드) <= key(자식 노드)
힙의 동작 과정
삽입
최대 힙에 저장할 때
최대 힙에 35라는 값을 추가한다고 생각해보자. 완전 이진 트리의 규칙에 맞춰 가장 왼쪽 아래에 노드가 생기지만 이는 최대 힙 규칙에 맞지 않는다.
그럼 새로 입력된 노드와 부모 노드의 값을 비교하게 되고 최대 힙 조건인 부모 노드의 key >= 자식 노드의 key를 만족하기 위해 위치를 바꿔준다.
이렇게 계속해서 부모 노드와 키 값을 비교하면서 최대 힙 조건에 충족할 때 까지 자리를 swap 한다.
최소 힙에 삽입할 때
이번에는 최소 힙에 데이터를 삽입 하는 경우를 생각해보자. 이것도 최대 힙과 개념은 크게 다르지 않다. 다만 최소 힙의 조건인 부모 노드의 key <= 자식 노드의 key만 만족해주면 된다.
이 과정을 계속 반복해주며 최소 힙 조건이 충족 될 때 까지 값을 이동시켜 준다.
삭제
최대 힙에서 삭제할 때
루트 값(최댓값)인 50을 반환하고 삭제한다고 생각해보자.
루트가 제거되면 최대 힙의 마지막 노드의 값을 루트 노드로 가져오게 된다.
그 후, 새로운 루트 노드와 자식 노드의 값을 비교하고, 만일 부모 노드보다 자식 노드가 둘다 크다면 둘중에 큰 값을, 둘중에 하나만 크다면 그 값과 swap 한다. 이를 최대 힙 조건이 만족할 때 까지 계속 반복한다.
최소 힙에서 삭제할 때
루트 값(최솟값)인 1을 반환하고 삭제한다고 생각해보자.
이때도 최대 힙에서 삭제할때와 마찬가지로 마지막 노드를 루트 노드로 가져와서 값을 비교해가며 최소 힙의 조건이 맞을 때 까지 진행한다.
최소 힙 경우는 자식 노드와 부모 노드를 비교하여 자식 노드중 가장 작은값이 위로 올라오게 된다.
Heapify
Heapify란 이미 값들이 채워진 완전 이진트리가 있을 때, 새로운 값을 추가하거나 삭제하는 경우에 완전 이진트리의 성질이 깨지는 경우가 존재한다. 이때, 깨진 트리의 값을 다시 맞추는 작업을 말한다. 위에서 삽입, 삭제시에 값을 비교해 가며 힙의 구조를 유지해가는 과정이라고 생각하면 된다.
힙의 연산별 시간 복잡도
| 연산 | 시간 복잡도 | 설명 |
| 삽입 | O(logn) | 새로운 요소를 힙의 가장 끝에 추가한 뒤, 부모 노드와 비교하면서 노드를 위로 올린다. 이때 최악의 경우 트리의 높이인 logn까지 연산을 해야 하므로 시간 복잡도는 O(logn)이 된다. |
| 삭제 | O(logn) | 루트 노드에서 값을 꺼내고 가장 마지막에 있는 노드를 루트로 올린 뒤 자식 노드와 비교하며 아래로 내린다. 이때도 삽입연산과 마찬가지로 트리의 높이까지 연산을 해야할 수 있으므로 시간 복잡도는 O(logn)이 된다. |
| 탐색 | 최댓값/최솟값 탐색 : O(1) 일반 값 탐색 : O(n) |
최댓값, 최솟값은 항상 루트 노드에 있으니 시간 복잡도는 O(1), 하지만 특정한 값을 찾을 때는 전체를 다 뒤져야 하므로 시간 복잡도가 O(n)이 된다. |
코드 구현
최대 힙 코드
class MaxHeap:
def __init__(self):
self.heap = [None] # 루트 노드의 인덱스를 1로 하기 위해 None을 넣어둔다.
def insert(self, value):
self.heap.append(value)
idx = len(self.heap) - 1 # 새로 추가된 노드의 인덱스값(None이 이미 들어있었기 때문)
while idx > 1:
parent_idx = idx // 2 # 부모 인덱스가 N일때, 왼쪽 자식은 2N, 오른쪽 자식은 2N+1
if self.heap[idx] > self.heap[parent_idx]: # 새로 추가된 노드의 값이 부모 노드보다 크다면 swap 해줘야함
self.heap[idx], self.heap[parent_idx] = self.heap[parent_idx], self.heap[idx]
idx = parent_idx # 새로 추가된 노드가 이제 부모 노드가 되었으므로 인덱스를 바꿔준다.
else:
break
def delete(self):
if len(self.heap) <= 1: # 인덱스가 1 이하라는 뜻은 기존에 미리 넣어둔 None말고는 아무값도 없다는 뜻
return None
max_heap = self.heap[1] # 최대 힙에서 최댓값은 항상 루트 노드에 존재하기 때문
if len(self.heap) <= 1: # 뽑은 값이 최댓값이자 유일한 값이었다면 바로 최댓값 리턴
return max_heap
last_val = self.heap.pop() # 삭제 후에 힙의 가장 마지막 값을 루트로 올려줘야 하기 때문
self.heap[1] = last_val # 힙 구조를 유지하기 위해 마지막 값을 루트 노드로 올림
self.down_heapify(1) # 위의 insert를 다시 돌며 제자리 찾기
return max_heap # 노드가 힙 구조에 맞춰지고 최댓값 반환
def down_heapify(self, idx):
while idx * 2 < len(self.heap):
left_child = idx * 2
right_child = idx * 2 + 1
current = idx
# 왼쪽 자식과 현재 값과의 1차 비교
if self.heap[left_child] > self.heap[current]:
current = left_child
# 오른쪽 자식과의 2차 비교
if right_child < len(self.heap) and self.heap[right_child] > self.heap[current]:
current = right_child
# 자식과 비교 후 부모가 가장 크다면 그대로 반목문 종료
if current == idx:
break
# 더 큰 자식이 있다면 그 자식과 현재 값을 swap
self.heap[idx], self.heap[current] = self.heap[current], self.heap[idx]
idx = current
def print_heap(self):
print(self.heap[1:])
Mh = MaxHeap()
Mh.insert(10)
Mh.insert(20)
Mh.insert(30)
Mh.insert(40)
Mh.insert(50)
Mh.print_heap()
print(Mh.delete())
Mh.print_heap()
print(Mh.delete())
Mh.print_heap()
'''
결과값
[50, 40, 20, 10, 30]
50
[40, 30, 20, 10]
40
[30, 10, 20]
'''최소 힙 코드 (부모와 자식을 비교하는 곳의 부등호 방향만 반대로 해주면 된다.)
class MinHeap:
def __init__(self):
self.heap = [None] # 루트 노드의 인덱스를 1로 하기 위해 None을 넣어둔다.
def insert(self, value):
self.heap.append(value)
idx = len(self.heap) - 1 # 새로 추가된 노드의 인덱스값(None이 이미 들어있었기 때문)
while idx > 1:
parent_idx = idx // 2 # 부모 인덱스가 N일때, 왼쪽 자식은 2N, 오른쪽 자식은 2N+1
if self.heap[idx] < self.heap[parent_idx]: # 새로 추가된 노드의 값이 부모 노드보다 작다면 swap 해줘야함
self.heap[idx], self.heap[parent_idx] = self.heap[parent_idx], self.heap[idx]
idx = parent_idx # 새로 추가된 노드가 이제 부모 노드가 되었으므로 인덱스를 바꿔준다.
else:
break
def delete(self):
if len(self.heap) <= 1: # 인덱스가 1 이하라는 뜻은 기존에 미리 넣어둔 None말고는 아무값도 없다는 뜻
return None
min_heap = self.heap[1] # 최소 힙에서 최솟값은 항상 루트 노드에 존재하기 때문
if len(self.heap) <= 1: # 뽑은 값이 최솟값이자 유일한 값이었다면 바로 최솟값 리턴
return min_heap
last_val = self.heap.pop() # 삭제 후에 힙의 가장 마지막 값을 루트로 올려줘야 하기 때문
self.heap[1] = last_val # 힙 구조를 유지하기 위해 마지막 값을 루트 노드로 올림
self.down_heapify(1) # 위의 insert를 다시 돌며 제자리 찾기
return min_heap # 노드가 힙 구조에 맞춰지고 최솟값 반환
def down_heapify(self, idx):
while idx * 2 < len(self.heap):
left_child = idx * 2
right_child = idx * 2 + 1
current = idx
# 왼쪽 자식과 현재 값과의 1차 비교
if self.heap[left_child] < self.heap[current]:
current = left_child
# 오른쪽 자식과의 2차 비교
if right_child < len(self.heap) and self.heap[right_child] < self.heap[current]:
current = right_child
# 자식과 비교 후 부모가 가장 작다면 그대로 반목문 종료
if current == idx:
break
# 더 작은 자식이 있다면 그 자식과 현재 값을 swap
self.heap[idx], self.heap[current] = self.heap[current], self.heap[idx]
idx = current
def print_heap(self):
print(self.heap[1:])
mh = MinHeap()
mh.insert(10)
mh.insert(20)
mh.insert(30)
mh.insert(40)
mh.insert(50)
mh.print_heap()
print(mh.delete())
mh.print_heap()
print(mh.delete())
mh.print_heap()
'''
결과값
[10, 20, 30, 40, 50]
10
[20, 40, 30, 50]
20
[30, 40, 50]
''''자료구조, 알고리즘' 카테고리의 다른 글
| 버블 정렬 (Bubble Sort) (0) | 2026.06.10 |
|---|---|
| 정렬 알고리즘 (0) | 2026.06.10 |
| 공간 복잡도 (0) | 2026.06.07 |
| 시간 복잡도 (0) | 2026.06.07 |
| 해시 테이블 (Hash Table) (0) | 2026.06.05 |