이미지 로딩 중...
AI Generated
2025. 11. 8. · 4 Views
Min Heap과 Max Heap 완벽 구현 가이드
힙(Heap) 자료구조의 핵심 개념인 Min Heap과 Max Heap을 처음부터 끝까지 구현해봅니다. 우선순위 큐, 스케줄링 시스템 등 실무에서 자주 사용되는 힙의 원리와 구현 방법을 상세히 다룹니다.
목차
- Heap 자료구조 기초
- Min Heap 기본 구조
- Heap Insert 연산
- Heap Extract 연산
- Heapify 과정
- Max Heap 구현
- 힙 기반 우선순위 큐
- 힙 정렬 알고리즘
1. Heap 자료구조 기초
시작하며
여러분이 실시간 채팅 애플리케이션을 개발하고 있는데, 수천 개의 메시지가 들어올 때 가장 중요한 메시지를 먼저 처리해야 하는 상황을 겪어본 적 있나요? 또는 운영체제의 프로세스 스케줄링에서 우선순위가 높은 작업을 빠르게 찾아야 하는 경우는 어떨까요?
이런 문제는 실제 개발 현장에서 자주 발생합니다. 단순히 배열이나 리스트를 사용하면 최댓값이나 최솟값을 찾는 데 O(n) 시간이 걸리고, 정렬된 상태를 유지하려면 삽입할 때마다 O(n) 시간이 필요합니다.
이는 대규모 시스템에서 심각한 성능 저하를 일으킵니다. 바로 이럴 때 필요한 것이 Heap 자료구조입니다.
힙은 최댓값이나 최솟값을 O(1)에 찾고, 삽입과 삭제를 O(log n)에 처리할 수 있어 우선순위 기반 작업에 최적화되어 있습니다.
개요
간단히 말해서, 힙은 완전 이진 트리(Complete Binary Tree) 형태를 가지며 부모-자식 간에 특정한 순서 관계를 유지하는 자료구조입니다. 힙이 필요한 이유는 우선순위를 가진 데이터를 효율적으로 관리하기 위해서입니다.
예를 들어, 병원 응급실에서 환자의 위급도에 따라 진료 순서를 정하거나, 네트워크 패킷을 중요도에 따라 전송하는 경우에 매우 유용합니다. 기존에는 우선순위 큐를 배열로 구현하여 매번 전체를 탐색하거나 정렬해야 했다면, 이제는 힙을 사용하여 로그 시간 복잡도로 효율적으로 처리할 수 있습니다.
힙의 핵심 특징은 다음과 같습니다. 첫째, 완전 이진 트리 구조로 배열로 표현하기 쉽습니다.
둘째, Min Heap은 부모가 자식보다 작고, Max Heap은 부모가 자식보다 큽니다. 셋째, 형제 노드 간에는 순서 관계가 없어 유연합니다.
이러한 특징들이 삽입과 삭제 연산을 빠르게 만들고, 메모리를 연속적으로 사용할 수 있게 합니다.
코드 예제
class MinHeap:
def __init__(self):
# 힙을 저장할 리스트 (인덱스 0은 사용하지 않음)
self.heap = [0]
self.size = 0
def parent(self, i):
# 부모 노드의 인덱스: i // 2
return i // 2
def left_child(self, i):
# 왼쪽 자식 노드의 인덱스: i * 2
return i * 2
def right_child(self, i):
# 오른쪽 자식 노드의 인덱스: i * 2 + 1
return i * 2 + 1
설명
이것이 하는 일: 힙 자료구조의 기본 골격을 정의합니다. 힙을 배열로 표현하고, 부모-자식 관계를 인덱스로 계산하는 핵심 메서드를 제공합니다.
첫 번째로, __init__ 메서드는 힙을 초기화합니다. self.heap = [0]으로 시작하는 이유는 인덱스 1부터 사용하여 부모-자식 관계 계산을 단순화하기 위해서입니다.
인덱스 1부터 시작하면 부모는 i//2, 왼쪽 자식은 i2, 오른쪽 자식은 i2+1로 간단하게 계산됩니다. 그 다음으로, parent, left_child, right_child 메서드가 실행되면서 노드 간의 관계를 쉽게 탐색할 수 있게 합니다.
이는 완전 이진 트리의 수학적 성질을 활용한 것으로, 별도의 포인터나 참조 없이도 트리 구조를 표현할 수 있습니다. 마지막으로, self.size가 현재 힙에 저장된 요소의 개수를 추적하여 최종적으로 삽입과 삭제 연산 시 힙의 경계를 정확히 파악할 수 있게 합니다.
여러분이 이 코드를 사용하면 메모리를 연속적으로 사용하여 캐시 효율성이 높고, 포인터 기반 트리보다 구현이 간단하며, 배열의 인덱스만으로 빠른 탐색이 가능한 이점을 얻을 수 있습니다.
실전 팁
💡 인덱스 0을 사용하지 않고 1부터 시작하면 부모-자식 계산이 매우 간단해집니다. 만약 0부터 시작하면 left_child는 2i+1, right_child는 2i+2, parent는 (i-1)//2로 복잡해집니다.
💡 흔한 실수는 size를 업데이트하지 않는 것입니다. 삽입과 삭제 시 반드시 size를 증가/감소시켜야 힙의 범위를 정확히 유지할 수 있습니다.
💡 실무에서는 제네릭 타입을 지원하도록 구현하세요. 숫자뿐 아니라 커스텀 객체도 비교 함수를 통해 힙에 저장할 수 있어야 합니다.
💡 디버깅 시에는 __str__ 메서드를 추가하여 힙의 현재 상태를 시각적으로 확인하면 문제를 빠르게 찾을 수 있습니다.
💡 대규모 데이터를 다룰 때는 초기 용량을 지정하여 배열 재할당 비용을 줄이세요. Python의 경우 리스트는 자동으로 크기를 조정하지만, 초기 크기를 예약하면 성능이 향상됩니다.
2. Min Heap 기본 구조
시작하며
여러분이 이벤트 기반 시뮬레이션 시스템을 개발하고 있는데, 수만 개의 이벤트 중에서 가장 빠른 시간에 발생할 이벤트를 계속 찾아야 하는 상황이라면 어떻게 하시겠어요? 매번 전체 리스트를 순회하는 것은 비효율적입니다.
이런 문제는 실시간 시스템, 운영체제 스케줄러, 네트워크 라우팅 등에서 필수적으로 해결해야 합니다. 최솟값을 빠르게 찾지 못하면 시스템 전체의 응답 시간이 느려지고 사용자 경험이 저하됩니다.
바로 이럴 때 필요한 것이 Min Heap입니다. Min Heap은 루트에 항상 최솟값이 위치하므로 O(1) 시간에 최솟값을 조회할 수 있고, 삽입과 삭제도 O(log n)으로 매우 효율적입니다.
개요
간단히 말해서, Min Heap은 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같은 완전 이진 트리입니다. Min Heap이 필요한 이유는 최솟값을 지속적으로 추출해야 하는 상황에서 최적의 성능을 제공하기 때문입니다.
예를 들어, 다익스트라 알고리즘에서 최단 거리 노드를 찾거나, 작업 스케줄러에서 가장 빠른 마감 시한을 가진 작업을 선택할 때 필수적입니다. 기존에는 정렬된 배열을 사용하여 최솟값은 O(1)에 찾지만 삽입은 O(n)이 걸렸다면, 이제는 Min Heap을 사용하여 둘 다 효율적으로 처리할 수 있습니다.
Min Heap의 핵심 특징은 다음과 같습니다. 첫째, 루트가 전체 힙에서 최솟값임이 보장됩니다.
둘째, 모든 서브트리도 Min Heap 속성을 만족합니다. 셋째, 형제 노드 간에는 대소 관계가 없어 삽입과 삭제가 유연합니다.
이러한 특징들이 우선순위 큐를 구현하는 가장 효율적인 방법을 제공합니다.
코드 예제
class MinHeap:
def __init__(self):
self.heap = [0]
self.size = 0
def peek(self):
# 최솟값 조회 (제거하지 않음)
if self.size == 0:
return None
return self.heap[1]
def is_empty(self):
# 힙이 비어있는지 확인
return self.size == 0
def get_size(self):
# 현재 힙의 크기 반환
return self.size
설명
이것이 하는 일: Min Heap의 기본적인 조회와 상태 확인 기능을 제공합니다. 힙에 저장된 최솟값을 제거하지 않고 확인하고, 힙의 상태를 체크할 수 있습니다.
첫 번째로, peek 메서드는 힙의 루트 요소를 반환합니다. Min Heap의 성질상 루트는 항상 최솟값이므로, 인덱스 1의 요소를 반환하기만 하면 됩니다.
빈 힙인 경우를 체크하여 None을 반환함으로써 안전성을 보장합니다. 그 다음으로, is_empty와 get_size 메서드가 실행되면서 힙의 현재 상태를 파악할 수 있게 합니다.
이는 힙을 사용하는 상위 레벨 알고리즘에서 종료 조건을 판단하거나 용량을 체크할 때 필수적입니다. 마지막으로, 이러한 기본 메서드들이 힙의 내부 구조를 노출하지 않으면서도 최종적으로 필요한 정보를 제공하여 캡슐화와 정보 은닉 원칙을 지킵니다.
여러분이 이 코드를 사용하면 힙의 상태를 안전하게 확인하고, 최솟값을 빠르게 조회하며, 비어있는 힙에 대한 안전한 처리가 가능한 이점을 얻을 수 있습니다.
실전 팁
💡 peek 메서드는 O(1) 시간 복잡도로 매우 빠르므로, 최솟값을 자주 확인해야 하는 경우 부담 없이 호출할 수 있습니다.
💡 흔한 실수는 빈 힙에서 peek를 호출할 때 예외를 발생시키지 않는 것입니다. None을 반환하거나 명시적인 예외를 던지도록 일관성 있게 구현하세요.
💡 실무에서는 peek 대신 get_min이나 top 같은 더 명확한 이름을 사용하는 것도 좋습니다. Python의 heapq 모듈은 heap[0]으로 직접 접근합니다.
💡 멀티스레드 환경에서는 peek와 extract 사이에 다른 스레드가 개입할 수 있으므로, 락을 사용하거나 원자적 연산을 보장해야 합니다.
💡 디버깅 시에는 힙의 불변성을 검증하는 is_valid_heap 메서드를 추가하여 모든 부모-자식 쌍이 Min Heap 속성을 만족하는지 확인하세요.
3. Heap Insert 연산
시작하며
여러분이 실시간 주식 거래 시스템에서 새로운 매수 주문이 들어올 때마다 가장 낮은 가격의 주문을 즉시 찾아야 하는 상황이라면? 단순히 리스트 끝에 추가하면 정렬이 깨지고, 매번 정렬하면 너무 느립니다.
이런 문제는 동적으로 데이터가 추가되면서도 우선순위 순서를 유지해야 하는 모든 시스템에서 발생합니다. 삽입할 때마다 전체를 재정렬하면 O(n log n)이 걸리고, 이는 실시간 시스템에서는 용납될 수 없습니다.
바로 이럴 때 필요한 것이 Heap의 Insert 연산입니다. 새 요소를 힙의 끝에 추가한 후, "상향 조정(Bubble Up)" 과정을 통해 O(log n) 시간에 힙 속성을 복원합니다.
개요
간단히 말해서, Heap Insert는 새 요소를 완전 이진 트리의 마지막 위치에 추가한 후, 부모와 비교하며 올바른 위치를 찾아 올라가는 연산입니다. Insert 연산이 필요한 이유는 힙의 구조적 불변성과 순서 불변성을 모두 유지하면서 새 데이터를 추가하기 위해서입니다.
예를 들어, 이벤트 시뮬레이터에서 새로운 이벤트가 생성되거나, 작업 큐에 새 작업이 추가될 때 우선순위 순서를 자동으로 유지합니다. 기존에는 이진 탐색 트리에 삽입하여 O(log n)을 달성했지만 균형이 깨지면 O(n)까지 느려졌다면, 이제는 힙을 사용하여 항상 O(log n)을 보장할 수 있습니다.
Insert 연산의 핵심 특징은 다음과 같습니다. 첫째, 완전 이진 트리의 형태를 유지하기 위해 항상 마지막 위치에 추가합니다.
둘째, Bubble Up(상향 조정) 과정으로 부모와 비교하며 올라갑니다. 셋째, 최악의 경우 트리의 높이만큼만 이동하므로 O(log n)입니다.
이러한 특징들이 동적 우선순위 관리를 효율적으로 만듭니다.
코드 예제
class MinHeap:
def insert(self, value):
# 힙의 끝에 새 값을 추가
self.heap.append(value)
self.size += 1
# 추가된 위치에서 상향 조정 시작
self._bubble_up(self.size)
def _bubble_up(self, i):
# 루트에 도달하거나 부모보다 크거나 같으면 종료
while i // 2 > 0:
parent_idx = i // 2
# 부모보다 작으면 교환
if self.heap[i] < self.heap[parent_idx]:
self.heap[i], self.heap[parent_idx] = \
self.heap[parent_idx], self.heap[i]
i = parent_idx
설명
이것이 하는 일: 새로운 요소를 Min Heap에 추가하면서 힙의 순서 속성을 유지합니다. 완전 이진 트리의 구조를 깨지 않으면서 효율적으로 삽입합니다.
첫 번째로, insert 메서드는 새 값을 self.heap의 끝에 추가하고 size를 증가시킵니다. 배열의 끝에 추가하는 것은 완전 이진 트리의 마지막 레벨 가장 오른쪽 위치에 노드를 추가하는 것과 같으며, 이는 O(1) 연산입니다.
그 다음으로, _bubble_up 메서드가 실행되면서 새로 추가된 요소가 부모보다 작은 경우 계속 위로 올라갑니다. while i // 2 > 0 조건은 루트(인덱스 1)에 도달할 때까지 반복하며, 각 단계에서 부모와 비교하여 Min Heap 속성을 위반하면 교환합니다.
세 번째로, 교환 후 i = parent_idx로 인덱스를 업데이트하여 다시 그 위치의 부모와 비교합니다. 이 과정은 부모보다 크거나 같은 위치를 찾거나 루트에 도달할 때까지 계속됩니다.
마지막으로, 이 알고리즘이 트리의 높이에 비례하는 시간만 소요하므로 최종적으로 O(log n) 시간 복잡도를 달성합니다. n개의 요소가 있는 완전 이진 트리의 높이는 log n이기 때문입니다.
여러분이 이 코드를 사용하면 동적으로 데이터가 추가되는 환경에서도 항상 최솟값을 빠르게 찾을 수 있고, 삽입 성능이 예측 가능하며, 메모리를 연속적으로 사용하여 캐시 친화적인 이점을 얻을 수 있습니다.
실전 팁
💡 Bubble Up의 반대 개념인 Bubble Down(또는 Heapify Down)도 함께 이해하면 힙의 전체 동작을 완전히 파악할 수 있습니다.
💡 흔한 실수는 size를 증가시키지 않거나, append 후 bubble_up의 시작 인덱스를 잘못 지정하는 것입니다. 반드시 self.size를 먼저 증가시키고 그 값을 사용하세요.
💡 성능 최적화를 위해 실제로 값을 교환하는 대신, 삽입할 위치를 찾을 때까지 부모를 아래로 복사하고 마지막에 한 번만 삽입하는 방법도 있습니다.
💡 제네릭 타입을 지원할 때는 비교 연산자를 커스터마이징할 수 있도록 comparator 함수를 받는 것이 좋습니다. Python의 경우 functools.total_ordering을 활용하세요.
💡 디버깅 시에는 각 bubble_up 단계마다 힙을 출력하여 요소가 올바르게 이동하는지 확인하면 문제를 빠르게 발견할 수 있습니다.
4. Heap Extract 연산
시작하며
여러분이 작업 스케줄러를 개발하는데, 가장 우선순위가 높은(가장 이른 마감 시한의) 작업을 꺼내서 실행하고, 그 다음 우선순위 작업을 즉시 찾아야 하는 상황이라면? 단순히 리스트에서 제거하면 다음 최솟값을 찾는 데 O(n)이 걸립니다.
이런 문제는 우선순위 큐의 핵심 연산으로, CPU 스케줄링, 네트워크 패킷 처리, 이벤트 처리 등 모든 실시간 시스템에서 필수적입니다. 최솟값을 제거한 후 다음 최솟값을 빠르게 찾지 못하면 시스템 전체가 느려집니다.
바로 이럴 때 필요한 것이 Heap의 Extract 연산입니다. 루트를 제거하고, 마지막 요소를 루트로 옮긴 후, "하향 조정(Bubble Down)" 과정을 통해 O(log n) 시간에 힙 속성을 복원합니다.
개요
간단히 말해서, Heap Extract(또는 Extract-Min)는 루트 노드(최솟값)를 제거하고, 힙의 마지막 요소를 루트로 옮긴 후, 자식들과 비교하며 내려가면서 올바른 위치를 찾는 연산입니다. Extract 연산이 필요한 이유는 최솟값을 가져오는 동시에 나머지 요소들이 여전히 힙 속성을 만족하도록 재구성하기 위해서입니다.
예를 들어, 다익스트라 알고리즘에서 최단 거리 노드를 꺼내거나, 이벤트 루프에서 다음 이벤트를 처리할 때 필수적입니다. 기존에는 정렬된 배열에서 첫 요소를 제거하면 나머지를 앞으로 이동시켜야 해서 O(n)이 걸렸다면, 이제는 힙을 사용하여 O(log n)으로 효율적으로 처리할 수 있습니다.
Extract 연산의 핵심 특징은 다음과 같습니다. 첫째, 항상 루트(최솟값)를 제거하므로 우선순위가 보장됩니다.
둘째, 마지막 요소를 루트로 옮겨 완전 이진 트리 형태를 유지합니다. 셋째, Bubble Down(하향 조정)으로 두 자식 중 작은 쪽과 비교하며 내려갑니다.
이러한 특징들이 지속적으로 최솟값을 추출하는 알고리즘을 효율적으로 만듭니다.
코드 예제
class MinHeap:
def extract_min(self):
# 빈 힙이면 None 반환
if self.size == 0:
return None
# 루트(최솟값) 저장
min_val = self.heap[1]
# 마지막 요소를 루트로 이동
self.heap[1] = self.heap[self.size]
self.size -= 1
self.heap.pop()
# 루트에서 하향 조정 시작
if self.size > 0:
self._bubble_down(1)
return min_val
def _bubble_down(self, i):
while i * 2 <= self.size:
# 두 자식 중 작은 쪽 선택
min_child_idx = self._get_min_child(i)
# 자식보다 크면 교환
if self.heap[i] > self.heap[min_child_idx]:
self.heap[i], self.heap[min_child_idx] = \
self.heap[min_child_idx], self.heap[i]
else:
break
i = min_child_idx
def _get_min_child(self, i):
# 오른쪽 자식이 없으면 왼쪽 반환
if i * 2 + 1 > self.size:
return i * 2
# 두 자식 중 작은 쪽 반환
if self.heap[i * 2] < self.heap[i * 2 + 1]:
return i * 2
return i * 2 + 1
설명
이것이 하는 일: Min Heap에서 최솟값(루트)을 제거하고, 나머지 요소들이 여전히 힙 속성을 만족하도록 재구성합니다. 완전 이진 트리의 형태를 유지하면서 효율적으로 삭제합니다.
첫 번째로, extract_min 메서드는 루트 요소(self.heap[1])를 저장하고, 힙의 마지막 요소를 루트 위치로 이동시킵니다. 이는 완전 이진 트리의 마지막 노드를 제거하여 구조를 유지하는 것과 같습니다.
size를 감소시키고 배열에서 pop하여 메모리를 정리합니다. 그 다음으로, _bubble_down 메서드가 실행되면서 새로운 루트 요소가 자식들과 비교됩니다.
while i * 2 <= self.size 조건으로 왼쪽 자식이 존재하는 동안 계속 내려가며, 각 단계에서 두 자식 중 작은 값을 선택합니다. 세 번째로, _get_min_child 메서드가 두 자식 중 더 작은 값의 인덱스를 반환합니다.
오른쪽 자식이 없는 경우(i*2+1 > size)는 왼쪽 자식만 반환하고, 둘 다 있으면 값을 비교하여 작은 쪽을 선택합니다. 이는 Min Heap 속성을 만족시키는 데 중요합니다.
네 번째로, 현재 노드가 선택된 자식보다 크면 교환하고 인덱스를 업데이트하여 계속 내려갑니다. 만약 자식보다 작거나 같으면 올바른 위치를 찾은 것이므로 break로 종료합니다.
마지막으로, 이 알고리즘이 트리의 높이만큼만 이동하므로 최종적으로 O(log n) 시간 복잡도를 달성합니다. 저장해둔 min_val을 반환하여 호출자에게 최솟값을 전달합니다.
여러분이 이 코드를 사용하면 우선순위 큐의 핵심 기능인 최솟값 추출을 효율적으로 수행하고, 지속적으로 데이터를 처리하면서도 성능을 유지하며, 힙 정렬 같은 고급 알고리즘의 기반을 마련할 수 있는 이점을 얻을 수 있습니다.
실전 팁
💡 Extract 연산에서 가장 중요한 부분은 두 자식 중 작은 쪽을 선택하는 것입니다. 큰 쪽과 교환하면 Min Heap 속성이 깨집니다.
💡 흔한 실수는 오른쪽 자식이 없는 경우를 처리하지 않는 것입니다. 완전 이진 트리의 마지막 레벨에서는 오른쪽 자식이 없을 수 있으므로 경계 검사가 필수입니다.
💡 성능 최적화를 위해 교환 대신 hole(구멍)을 아래로 이동시키고 마지막에 한 번만 삽입하는 Floyd's heap construction 기법을 사용할 수 있습니다.
💡 멀티스레드 환경에서는 extract와 insert가 동시에 발생할 수 있으므로, 전체 연산을 원자적으로 만들거나 락프리 자료구조를 고려하세요.
💡 디버깅 시에는 extract 후 힙이 여전히 유효한지 검증하는 테스트를 추가하여 모든 부모-자식 쌍이 Min Heap 속성을 만족하는지 확인하세요.
5. Heapify 과정
시작하며
여러분이 정렬되지 않은 대량의 데이터를 받았는데, 이를 힙으로 변환해야 하는 상황이라면? 하나씩 insert를 호출하면 n개 요소에 대해 각각 O(log n)이므로 총 O(n log n)이 걸립니다.
더 빠른 방법은 없을까요? 이런 문제는 초기 데이터셋을 힙으로 구성하거나, 힙 정렬을 수행하거나, 기존 배열을 제자리에서 힙으로 변환할 때 발생합니다.
효율적인 초기화 방법이 없다면 대규모 데이터 처리에서 병목이 됩니다. 바로 이럴 때 필요한 것이 Heapify 과정입니다.
배열을 상향식으로 처리하여 놀랍게도 O(n) 시간에 힙을 구성할 수 있습니다. 이는 개별 insert보다 훨씬 빠릅니다.
개요
간단히 말해서, Heapify는 정렬되지 않은 배열을 힙으로 변환하는 과정으로, 마지막 비리프 노드부터 시작하여 루트까지 각 노드에 대해 bubble_down을 수행합니다. Heapify가 필요한 이유는 대량의 데이터를 효율적으로 힙으로 초기화하기 위해서입니다.
예를 들어, 힙 정렬 알고리즘의 첫 단계나, 우선순위 큐를 기존 데이터로 초기화할 때 O(n) 시간에 처리할 수 있습니다. 기존에는 빈 힙에 n개 요소를 하나씩 insert하여 O(n log n)이 걸렸다면, 이제는 heapify를 사용하여 O(n)으로 더 빠르게 힙을 구성할 수 있습니다.
Heapify의 핵심 특징은 다음과 같습니다. 첫째, 상향식 접근으로 리프 노드는 이미 힙이므로 건너뜁니다.
둘째, 마지막 비리프 노드(n//2)부터 루트까지 역순으로 처리합니다. 셋째, 각 노드에 대해 bubble_down만 수행하여 서브트리를 힙으로 만듭니다.
이러한 특징들이 선형 시간 복잡도를 가능하게 합니다.
코드 예제
class MinHeap:
def __init__(self, arr=None):
self.heap = [0]
self.size = 0
# 배열이 주어지면 heapify 수행
if arr:
self.heap.extend(arr)
self.size = len(arr)
self._heapify()
def _heapify(self):
# 마지막 비리프 노드부터 루트까지 역순으로
start = self.size // 2
for i in range(start, 0, -1):
self._bubble_down(i)
def build_heap(self, arr):
# 기존 힙을 새 배열로 재구성
self.heap = [0] + arr
self.size = len(arr)
self._heapify()
설명
이것이 하는 일: 임의의 배열을 Min Heap으로 변환합니다. 개별 insert보다 훨씬 효율적인 O(n) 시간 복잡도로 힙을 구성합니다.
첫 번째로, __init__ 메서드가 배열을 받으면 self.heap에 추가하고 _heapify를 호출합니다. 인덱스 0을 사용하지 않으므로 self.heap = [0]로 시작하고 extend로 배열을 추가합니다.
이는 기존 배열을 복사하여 힙으로 사용할 수 있게 합니다. 그 다음으로, _heapify 메서드가 실행되면서 마지막 비리프 노드(self.size // 2)부터 시작합니다.
완전 이진 트리에서 인덱스 n//2+1부터 n까지는 모두 리프 노드이고, 리프 노드는 자식이 없으므로 이미 힙 속성을 만족합니다. 따라서 n//2부터 1까지만 처리하면 됩니다.
세 번째로, range(start, 0, -1)로 역순으로 반복하며 각 노드에 대해 _bubble_down을 호출합니다. 이는 하위 레벨부터 상위 레벨로 올라가면서 각 서브트리를 힙으로 만드는 상향식 접근입니다.
자식들이 이미 힙이므로 부모만 올바른 위치로 내리면 됩니다. 네 번째로, 시간 복잡도가 O(n)인 이유는 각 레벨의 노드 개수와 이동 거리의 곱을 합하면 수렴하기 때문입니다.
리프 노드는 이동하지 않고, 그 위 레벨은 최대 1번, 그 위는 최대 2번 이동하는 식으로 대부분의 노드는 짧은 거리만 이동합니다. 마지막으로, build_heap 메서드가 기존 힙을 완전히 새로운 배열로 재구성하는 기능을 제공하여 최종적으로 힙을 재사용할 수 있게 합니다.
여러분이 이 코드를 사용하면 대량의 초기 데이터를 빠르게 힙으로 변환하고, 힙 정렬 알고리즘을 효율적으로 구현하며, 메모리를 제자리에서 사용하여 추가 공간 없이 힙을 구성할 수 있는 이점을 얻을 수 있습니다.
실전 팁
💡 Heapify가 O(n)인 이유를 이해하려면 각 레벨의 노드 개수와 최대 이동 거리를 계산해보세요. Σ(h * n/2^h) = O(n)으로 수렴합니다.
💡 흔한 실수는 heapify를 순방향(1부터 n까지)으로 수행하는 것입니다. 반드시 역순으로 해야 하위 서브트리가 먼저 힙이 되어 상위 노드 처리가 올바르게 됩니다.
💡 Python의 heapq 모듈은 heapify를 제공하지만 Min Heap만 지원합니다. Max Heap이 필요하면 값에 -1을 곱하거나 직접 구현하세요.
💡 제자리 heapify는 추가 메모리를 사용하지 않지만 원본 배열을 수정합니다. 원본을 보존해야 하면 먼저 복사하세요.
💡 디버깅 시에는 heapify 전후의 배열을 비교하고, 각 단계마다 힙 유효성을 검증하여 알고리즘이 올바르게 동작하는지 확인하세요.
6. Max Heap 구현
시작하며
여러분이 게임 리더보드 시스템을 개발하는데, 항상 최고 점수를 가진 플레이어를 빠르게 찾아야 하는 상황이라면? 또는 CPU 스케줄러에서 가장 높은 우선순위를 가진 프로세스를 선택해야 한다면?
Min Heap으로는 최댓값을 찾기 어렵습니다. 이런 문제는 최댓값 기반 우선순위가 필요한 모든 시스템에서 발생합니다.
최고 수익 주문, 가장 중요한 알림, 최대 트래픽 경로 등 "가장 큰" 것을 추적해야 하는 경우가 많습니다. 바로 이럴 때 필요한 것이 Max Heap입니다.
Min Heap과 정반대로 부모가 자식보다 크거나 같아야 하며, 루트에 항상 최댓값이 위치합니다. 구현은 비교 방향만 바꾸면 됩니다.
개요
간단히 말해서, Max Heap은 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같은 완전 이진 트리입니다. Max Heap이 필요한 이유는 최댓값을 지속적으로 추출해야 하는 상황에서 최적의 성능을 제공하기 때문입니다.
예를 들어, 스트리밍 데이터에서 상위 K개 요소를 유지하거나, 작업 스케줄러에서 가장 높은 우선순위를 선택할 때 필수적입니다. 기존에는 Min Heap에 음수를 저장하여 우회적으로 Max Heap을 구현했다면, 이제는 직접 Max Heap을 구현하여 더 직관적이고 명확한 코드를 작성할 수 있습니다.
Max Heap의 핵심 특징은 다음과 같습니다. 첫째, 루트가 전체 힙에서 최댓값임이 보장됩니다.
둘째, Min Heap과 구조는 같지만 비교 방향만 반대입니다. 셋째, 모든 연산의 시간 복잡도가 Min Heap과 동일합니다.
이러한 특징들이 최댓값 기반 우선순위 시스템을 효율적으로 구현하게 합니다.
코드 예제
class MaxHeap:
def __init__(self):
self.heap = [0]
self.size = 0
def insert(self, value):
self.heap.append(value)
self.size += 1
self._bubble_up(self.size)
def _bubble_up(self, i):
# 부모보다 크면 교환 (Min Heap과 반대)
while i // 2 > 0:
parent_idx = i // 2
if self.heap[i] > self.heap[parent_idx]:
self.heap[i], self.heap[parent_idx] = \
self.heap[parent_idx], self.heap[i]
i = parent_idx
def extract_max(self):
if self.size == 0:
return None
max_val = self.heap[1]
self.heap[1] = self.heap[self.size]
self.size -= 1
self.heap.pop()
if self.size > 0:
self._bubble_down(1)
return max_val
def _bubble_down(self, i):
while i * 2 <= self.size:
max_child_idx = self._get_max_child(i)
# 자식보다 작으면 교환 (Min Heap과 반대)
if self.heap[i] < self.heap[max_child_idx]:
self.heap[i], self.heap[max_child_idx] = \
self.heap[max_child_idx], self.heap[i]
else:
break
i = max_child_idx
def _get_max_child(self, i):
if i * 2 + 1 > self.size:
return i * 2
# 두 자식 중 큰 쪽 반환 (Min Heap과 반대)
if self.heap[i * 2] > self.heap[i * 2 + 1]:
return i * 2
return i * 2 + 1
def peek(self):
if self.size == 0:
return None
return self.heap[1]
설명
이것이 하는 일: Max Heap 자료구조를 완전히 구현합니다. 최댓값을 O(1)에 조회하고 삽입/삭제를 O(log n)에 처리합니다.
첫 번째로, insert 메서드는 Min Heap과 동일하게 끝에 추가하지만, _bubble_up에서 비교 방향이 반대입니다. self.heap[i] > self.heap[parent_idx]로 현재 노드가 부모보다 크면 위로 올라가 Max Heap 속성을 유지합니다.
그 다음으로, extract_max 메서드가 실행되면서 루트(최댓값)를 제거하고 마지막 요소를 루트로 옮깁니다. 구조는 Min Heap의 extract_min과 완전히 같지만 메서드 이름이 의미를 명확히 합니다.
세 번째로, _bubble_down과 _get_max_child에서 비교 방향이 반대입니다. 자식 중 큰 쪽을 선택하고, 현재 노드가 그보다 작으면 교환합니다.
이는 Max Heap 속성(부모 ≥ 자식)을 만족시키기 위한 것입니다. 네 번째로, peek 메서드가 루트의 최댓값을 반환합니다.
이는 Min Heap의 peek와 동일하지만 의미적으로는 최댓값을 조회합니다. 마지막으로, 모든 연산의 시간 복잡도가 Min Heap과 동일하여 최종적으로 O(1) 조회, O(log n) 삽입/삭제를 달성합니다.
단지 비교 연산자만 바꾸었을 뿐입니다. 여러분이 이 코드를 사용하면 최댓값 기반 우선순위 시스템을 직관적으로 구현하고, Min Heap을 음수로 우회하지 않아 코드 가독성이 높아지며, 상위 K개 요소 추적 같은 고급 알고리즘을 효율적으로 작성할 수 있는 이점을 얻을 수 있습니다.
실전 팁
💡 Min Heap과 Max Heap을 부모 클래스로 추상화하고 비교 함수만 다르게 구현하면 코드 중복을 줄일 수 있습니다.
💡 흔한 실수는 _get_max_child에서 비교 방향을 바꾸지 않는 것입니다. Min Heap 코드를 복사할 때 모든 비교 연산자를 주의 깊게 확인하세요.
💡 Python의 heapq는 Min Heap만 지원하므로, Max Heap이 필요하면 값에 -1을 곱하거나 (value, data) 튜플에서 value를 음수로 저장하세요.
💡 제네릭 Max Heap을 만들 때는 Comparator 인터페이스를 받아 커스텀 비교 로직을 지원하면 더 유연합니다.
💡 디버깅 시에는 Min Heap과 Max Heap을 동시에 테스트하여 동일한 데이터에 대해 하나는 최솟값, 다른 하나는 최댓값을 올바르게 반환하는지 확인하세요.
7. 힙 기반 우선순위 큐
시작하며
여러분이 병원 응급실 관리 시스템을 개발하는데, 환자가 도착한 순서가 아니라 위급도에 따라 진료해야 하는 상황이라면? 단순 큐로는 우선순위를 처리할 수 없고, 매번 전체를 탐색하면 느립니다.
이런 문제는 운영체제의 프로세스 스케줄링, 네트워크 라우터의 패킷 처리, 이벤트 기반 시뮬레이션 등 우선순위가 있는 모든 작업 처리 시스템에서 발생합니다. 우선순위 큐가 없으면 중요한 작업이 지연됩니다.
바로 이럴 때 필요한 것이 힙 기반 우선순위 큐입니다. 힙을 내부 자료구조로 사용하여 삽입, 최우선순위 요소 추출, 우선순위 확인을 모두 효율적으로 처리합니다.
개요
간단히 말해서, 우선순위 큐는 각 요소가 우선순위를 가지며, 항상 가장 높은(또는 낮은) 우선순위를 가진 요소가 먼저 나오는 추상 자료형입니다. 힙으로 구현하면 모든 연산이 O(log n)입니다.
우선순위 큐가 필요한 이유는 일반 큐의 FIFO(선입선출) 순서가 아니라 중요도에 따라 처리해야 하는 실무 시나리오가 매우 많기 때문입니다. 예를 들어, CPU는 사용자 인터랙션을 백그라운드 작업보다 먼저 처리하고, 네트워크는 긴급 패킷을 일반 패킷보다 먼저 전송해야 합니다.
기존에는 정렬된 리스트로 구현하여 삽입이 O(n)이거나, 정렬되지 않은 리스트로 구현하여 추출이 O(n)이었다면, 이제는 힙을 사용하여 모든 연산을 O(log n)으로 균형 있게 처리할 수 있습니다. 우선순위 큐의 핵심 특징은 다음과 같습니다.
첫째, enqueue(삽입)와 dequeue(추출)가 우선순위에 따라 동작합니다. 둘째, peek로 최우선순위 요소를 제거하지 않고 확인할 수 있습니다.
셋째, 우선순위와 데이터를 함께 저장하여 복잡한 객체도 관리할 수 있습니다. 이러한 특징들이 실무에서 가장 널리 사용되는 자료구조 중 하나가 되게 합니다.
코드 예제
class PriorityQueue:
def __init__(self, max_heap=False):
# max_heap=True면 높은 우선순위 먼저, False면 낮은 우선순위 먼저
self.heap = [0]
self.size = 0
self.max_heap = max_heap
def enqueue(self, priority, data):
# (우선순위, 데이터) 튜플로 저장
item = (priority, data)
self.heap.append(item)
self.size += 1
self._bubble_up(self.size)
def dequeue(self):
# 최우선순위 요소 제거 및 반환
if self.size == 0:
return None
item = self.heap[1]
self.heap[1] = self.heap[self.size]
self.size -= 1
self.heap.pop()
if self.size > 0:
self._bubble_down(1)
return item[1] # 데이터만 반환
def peek(self):
if self.size == 0:
return None
return self.heap[1][1] # 데이터만 반환
def _compare(self, i, j):
# Max Heap이면 큰 쪽이 우선, Min Heap이면 작은 쪽이 우선
if self.max_heap:
return self.heap[i][0] > self.heap[j][0]
return self.heap[i][0] < self.heap[j][0]
def _bubble_up(self, i):
while i // 2 > 0:
parent_idx = i // 2
if self._compare(i, parent_idx):
self.heap[i], self.heap[parent_idx] = \
self.heap[parent_idx], self.heap[i]
i = parent_idx
def _bubble_down(self, i):
while i * 2 <= self.size:
priority_child_idx = self._get_priority_child(i)
if not self._compare(i, priority_child_idx):
self.heap[i], self.heap[priority_child_idx] = \
self.heap[priority_child_idx], self.heap[i]
else:
break
i = priority_child_idx
def _get_priority_child(self, i):
if i * 2 + 1 > self.size:
return i * 2
if self._compare(i * 2, i * 2 + 1):
return i * 2
return i * 2 + 1
설명
이것이 하는 일: 우선순위 큐를 힙으로 구현합니다. Min Heap과 Max Heap을 선택할 수 있고, 우선순위와 데이터를 함께 저장하며, 표준 큐 인터페이스(enqueue, dequeue, peek)를 제공합니다.
첫 번째로, __init__ 메서드가 max_heap 매개변수를 받아 우선순위 방향을 결정합니다. True면 높은 숫자가 높은 우선순위(Max Heap), False면 낮은 숫자가 높은 우선순위(Min Heap)입니다.
이는 다양한 사용 사례를 지원합니다. 그 다음으로, enqueue 메서드가 실행되면서 (priority, data) 튜플을 힙에 추가합니다.
튜플은 Python에서 첫 번째 요소로 자동 비교되므로 우선순위 기반 정렬이 자연스럽게 이루어집니다. 이후 bubble_up으로 올바른 위치로 이동합니다.
세 번째로, dequeue 메서드가 최우선순위 요소를 제거하고 데이터만 반환합니다. 내부적으로는 (priority, data) 튜플이지만 사용자에게는 데이터만 보여주어 추상화를 제공합니다.
네 번째로, _compare 메서드가 max_heap 플래그에 따라 비교 로직을 결정합니다. 이 하나의 메서드가 Min Heap과 Max Heap의 동작을 통합하여 코드 중복을 줄입니다.
다섯 번째로, _bubble_up, _bubble_down, _get_priority_child가 모두 _compare를 사용하여 실행됩니다. 튜플의 첫 번째 요소(우선순위)를 기준으로 비교하므로 힙 속성이 우선순위에 대해 유지됩니다.
마지막으로, 이 구현이 우선순위 큐의 표준 인터페이스를 제공하면서 최종적으로 다양한 알고리즘(다익스트라, A*, 이벤트 시뮬레이션 등)의 기반이 됩니다. 여러분이 이 코드를 사용하면 우선순위 기반 작업 스케줄링을 쉽게 구현하고, Min/Max 우선순위를 유연하게 선택하며, 복잡한 객체에 우선순위를 부여하여 관리하고, 그래프 알고리즘 등 고급 알고리즘의 핵심 구성요소를 확보할 수 있는 이점을 얻을 수 있습니다.
실전 팁
💡 실무에서는 우선순위가 같은 경우를 처리하기 위해 (priority, timestamp, data) 형태로 저장하여 동일 우선순위는 FIFO로 처리하세요.
💡 흔한 실수는 우선순위와 데이터를 혼동하는 것입니다. enqueue는 (우선순위, 데이터)를 받지만 dequeue는 데이터만 반환해야 명확합니다.
💡 Python의 heapq.heappush/heappop을 사용하면 더 간단하지만, 내부 구조를 이해하기 위해 직접 구현하는 것이 학습에 도움이 됩니다.
💡 대규모 시스템에서는 우선순위 업데이트(decrease_key, increase_key) 연산도 필요할 수 있습니다. 이는 요소를 찾아 우선순위를 변경하고 재조정하는 것입니다.
💡 멀티스레드 환경에서는 threading.Lock을 사용하여 enqueue와 dequeue를 원자적으로 만들거나, queue.PriorityQueue 같은 스레드 안전한 구현을 사용하세요.
8. 힙 정렬 알고리즘
시작하며
여러분이 대용량 데이터를 정렬해야 하는데, 퀵 정렬은 최악의 경우 O(n²)이고, 병합 정렬은 O(n) 추가 메모리가 필요한 상황이라면? 항상 O(n log n)을 보장하면서도 제자리에서 정렬하는 방법은 없을까요?
이런 문제는 메모리가 제한적인 임베디드 시스템이나, 최악의 경우에도 성능을 보장해야 하는 실시간 시스템에서 발생합니다. 예측 가능한 성능과 작은 공간 복잡도가 모두 필요할 때 어려움을 겪습니다.
바로 이럴 때 필요한 것이 힙 정렬(Heap Sort)입니다. 힙을 이용하여 항상 O(n log n) 시간 복잡도를 보장하고, O(1) 추가 공간만 사용하며, 안정적인 성능을 제공합니다.
개요
간단히 말해서, 힙 정렬은 배열을 힙으로 만든 후, 반복적으로 최댓값(Max Heap) 또는 최솟값(Min Heap)을 추출하여 정렬하는 비교 기반 정렬 알고리즘입니다. 힙 정렬이 필요한 이유는 최악의 경우에도 O(n log n)을 보장하면서 제자리 정렬(in-place)이 가능하기 때문입니다.
예를 들어, 보안이 중요한 시스템에서 퀵 정렬의 최악 케이스를 피하거나, 메모리가 부족한 환경에서 병합 정렬 대신 사용할 때 유용합니다. 기존에는 퀵 정렬로 평균 O(n log n)이지만 최악 O(n²)이거나, 병합 정렬로 항상 O(n log n)이지만 O(n) 추가 메모리가 필요했다면, 이제는 힙 정렬로 두 장점을 모두 얻을 수 있습니다.
힙 정렬의 핵심 특징은 다음과 같습니다. 첫째, 시간 복잡도가 최선, 평균, 최악 모두 O(n log n)으로 일정합니다.
둘째, 제자리 정렬로 O(1) 추가 공간만 사용합니다. 셋째, 불안정 정렬(unstable)이므로 동일한 값의 상대적 순서가 유지되지 않습니다.
이러한 특징들이 예측 가능한 성능이 필요한 시스템에 적합하게 만듭니다.
코드 예제
def heap_sort(arr):
n = len(arr)
# 1단계: 배열을 Max Heap으로 변환 (heapify)
# 마지막 비리프 노드부터 루트까지
for i in range(n // 2 - 1, -1, -1):
_heapify_down(arr, n, i)
# 2단계: 하나씩 추출하여 정렬
for i in range(n - 1, 0, -1):
# 루트(최댓값)를 끝으로 이동
arr[0], arr[i] = arr[i], arr[0]
# 힙 크기를 줄이고 루트를 재조정
_heapify_down(arr, i, 0)
return arr
def _heapify_down(arr, heap_size, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
# 왼쪽 자식이 더 크면
if left < heap_size and arr[left] > arr[largest]:
largest = left
# 오른쪽 자식이 더 크면
if right < heap_size and arr[right] > arr[largest]:
largest = right
# 가장 큰 값이 루트가 아니면 교환하고 재귀
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
_heapify_down(arr, heap_size, largest)
설명
이것이 하는 일: 배열을 제자리에서 정렬합니다. 힙의 성질을 이용하여 최댓값을 반복적으로 찾아 배열의 끝부터 채워나갑니다.
첫 번째로, 초기 heapify 과정이 배열을 Max Heap으로 변환합니다. range(n // 2 - 1, -1, -1)로 마지막 비리프 노드부터 루트까지 역순으로 처리하여 O(n) 시간에 힙을 구성합니다.
이때 인덱스가 0부터 시작하므로 부모는 (i-1)//2, 자식은 2i+1, 2i+2입니다. 그 다음으로, 메인 정렬 루프가 실행되면서 range(n-1, 0, -1)로 역순으로 반복합니다.
각 단계에서 루트(최댓값)를 현재 힙의 마지막 위치와 교환하여 정렬된 영역을 뒤에서부터 확장합니다. 세 번째로, 교환 후 힙 크기를 하나 줄이고(i) 새로운 루트에 대해 _heapify_down을 호출합니다.
이는 힙 속성을 복원하여 다음 최댓값이 루트에 오도록 합니다. 네 번째로, _heapify_down 함수가 주어진 노드를 자식들과 비교하며 내려보냅니다.
두 자식 중 큰 쪽을 찾고, 현재 노드보다 크면 교환한 후 재귀적으로 처리합니다. heap_size 매개변수로 정렬된 영역을 제외합니다.
다섯 번째로, 전체 과정이 n번의 추출 * O(log n) heapify_down = O(n log n)입니다. 초기 heapify는 O(n)이므로 전체 시간 복잡도는 O(n log n)입니다.
마지막으로, 모든 연산이 배열 내에서 이루어져 최종적으로 O(1) 추가 공간만 사용합니다(재귀 스택 제외). 정렬이 완료되면 배열이 오름차순으로 정렬됩니다.
여러분이 이 코드를 사용하면 항상 예측 가능한 O(n log n) 성능을 보장받고, 메모리 제약이 있는 환경에서 효율적으로 정렬하며, 퀵 정렬의 최악 케이스를 피할 수 있고, 힙 자료구조의 실전 응용을 이해할 수 있는 이점을 얻을 수 있습니다.
실전 팁
💡 힙 정렬은 불안정 정렬이므로 동일한 값의 순서가 중요한 경우 병합 정렬을 사용하세요. 예를 들어, (이름, 나이)를 나이로 정렬할 때 이름 순서가 바뀔 수 있습니다.
💡 흔한 실수는 0-based 인덱싱에서 부모-자식 관계를 잘못 계산하는 것입니다. 부모는 (i-1)//2, 왼쪽 자식은 2i+1, 오른쪽 자식은 2i+2입니다.
💡 실무에서는 Python의 sorted()나 list.sort()가 Timsort를 사용하여 더 빠르지만, 힙 정렬은 최악 케이스 성능이 중요한 안전 시스템에 적합합니다.
💡 내림차순 정렬이 필요하면 Min Heap을 사용하거나, 정렬 후 배열을 역순으로 만드세요.
💡 대규모 데이터를 다룰 때는 외부 정렬(external sorting)에서 힙을 사용하여 k개의 정렬된 파일을 병합할 수 있습니다. k-way merge에 Min Heap을 사용하면 효율적입니다.