개요
Heap(힙) 자료구조는 완전 이진 트리(Complete Binary Tree)를 기반으로 하며, 각 부모 노드가 자식 노드보다 크거나(최대 힙, Max Heap) 작거나(최소 힙, Min Heap) 하는 특성을 가집니다. 이러한 구조 덕분에 힙은 Priority Queue나 Heap Sort (힙 정렬)과 같은 알고리즘에 많이 사용됩니다.
정의
- Heap 자료구조:
- 완전 이진 트리: 모든 레벨이 완전히 채워져 있으며, 마지막 레벨만 오른쪽부터 비워질 수 있음
- Heap 속성:
최대 힙(Max Heap): 각 부모 노드가 자식 노드보다 크거나 같다.최소 힙(Min Heap): 각 부모 노드가 자식 노드보다 작거나 같다.
- 주요 연산:
- 삽입(Insert): 새로운 요소를 추가한 후 힙 속성을 유지하도록 재구성
- 삭제(Delete)/추출(Extract): 루트 노드를 제거한 후 힙 재구성
- 조회(Peek): 루트 노드(최대 힙에서는 최대값, 최소 힙에서는 최소값)를 확인
예제
Python 예제
라이브러리 이용 (heapq 모듈)
import heapq
# 최소 힙(min-heap) 사용 예제
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print("최소 힙에서 추출한 최소 값:", heapq.heappop(heap)) # 출력: 1직접 구현
class MinHeap:
def __init__(self):
# 힙을 저장할 빈 리스트를 초기화
self.heap = []
def insert(self, value):
# 새로운 값을 힙의 마지막에 추가한 후, 힙 속성을 유지하기 위해 bubble up 실행
self.heap.append(value)
self._bubble_up(len(self.heap) - 1)
def _bubble_up(self, index):
# 현재 인덱스의 부모 노드 인덱스 계산
parent_index = (index - 1) // 2
# 현재 노드가 루트가 아니며, 부모 노드의 값이 현재 노드보다 큰 경우 교환
while index > 0 and self.heap[parent_index] > self.heap[index]:
# 부모 노드와 현재 노드의 값 교환
self.heap[parent_index], self.heap[index] = self.heap[index], self.heap[parent_index]
# 인덱스를 부모 인덱스로 업데이트하고, 재계산
index = parent_index
parent_index = (index - 1) // 2
def extract_min(self):
# 힙이 비어있는 경우 None 반환
if not self.heap:
return None
# 힙에 하나의 요소만 있는 경우 해당 요소 반환
if len(self.heap) == 1:
return self.heap.pop()
# 루트(최소값)를 저장하고, 마지막 요소를 루트 위치로 옮김
root = self.heap[0]
self.heap[0] = self.heap.pop()
# 루트에서부터 힙 속성을 복원하기 위해 heapify 실행
self._heapify(0)
return root
def _heapify(self, index):
# 현재 노드와 자식 노드들 중 최소값의 인덱스를 찾음
smallest = index
left = 2 * index + 1 # 왼쪽 자식 인덱스
right = 2 * index + 2 # 오른쪽 자식 인덱스
# 왼쪽 자식이 존재하며, 현재 최소값보다 작으면 smallest 업데이트
if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
smallest = left
# 오른쪽 자식이 존재하며, 현재 최소값보다 작으면 smallest 업데이트
if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
smallest = right
# 만약 최소값이 현재 인덱스가 아니라면 값을 교환 후 재귀적으로 heapify 호출
if smallest != index:
self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
self._heapify(smallest)
# 사용 예제
min_heap = MinHeap()
min_heap.insert(3)
min_heap.insert(1)
min_heap.insert(2)
print("직접 구현한 최소 힙에서 추출한 최소 값:", min_heap.extract_min()) # 출력: 1C++ 예제
라이브러리 이용
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
// 기본 priority_queue는 최대 힙(max-heap)입니다.
priority_queue<int> maxHeap;
maxHeap.push(3);
maxHeap.push(1);
maxHeap.push(2);
cout << "Max-Heap의 최대 값: " << maxHeap.top() << endl; // 출력: 3
// 최소 힙(min-heap) 구현: vector와 greater<int>를 사용
priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(3);
minHeap.push(1);
minHeap.push(2);
cout << "Min-Heap의 최소 값: " << minHeap.top() << endl; // 출력: 1
return 0;
}직접 구현
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 직접 구현한 최소 힙 클래스
class MinHeap {
private:
// 힙을 저장할 동적 배열
vector<int> heap;
// heapifyDown: 부모 노드에서 자식 노드로 내려가며 힙 속성을 복원하는 함수
void heapifyDown(int index) {
int smallest = index; // 현재 인덱스를 최소값으로 초기화
int left = 2 * index + 1; // 왼쪽 자식 인덱스 계산
int right = 2 * index + 2; // 오른쪽 자식 인덱스 계산
// 왼쪽 자식이 존재하며, 현재 노드보다 작으면 smallest 업데이트
if (left < heap.size() && heap[left] < heap[smallest])
smallest = left;
// 오른쪽 자식이 존재하며, 현재 노드보다 작으면 smallest 업데이트
if (right < heap.size() && heap[right] < heap[smallest])
smallest = right;
// 만약 최소값이 현재 노드가 아니라면, 값 교환 후 재귀 호출로 계속 heapify 수행
if (smallest != index) {
swap(heap[index], heap[smallest]);
heapifyDown(smallest);
}
}
// heapifyUp: 삽입된 노드가 부모와 비교하여 올바른 위치로 올라가도록 하는 함수
void heapifyUp(int index) {
// index가 0이 아니고, 부모 노드의 값이 현재 노드의 값보다 큰 경우
if (index && heap[(index - 1) / 2] > heap[index]) {
// 부모와 현재 노드의 값을 교환
swap(heap[index], heap[(index - 1) / 2]);
// 부모 인덱스에 대해 재귀적으로 heapifyUp 실행
heapifyUp((index - 1) / 2);
}
}
public:
// insert: 새 값을 힙에 삽입하고, heapifyUp을 호출하여 힙 속성 유지
void insert(int value) {
heap.push_back(value); // 힙의 마지막에 값 추가
heapifyUp(heap.size() - 1); // 추가된 값이 올바른 위치로 올라가도록 조정
}
// extractMin: 루트(최소값)를 추출하고, 힙을 재구성하는 함수
int extractMin() {
if (heap.empty()) return -1; // 힙이 비어있으면 -1 반환 (예외 처리 가능)
int root = heap[0]; // 루트(최소값) 저장
heap[0] = heap.back(); // 마지막 요소를 루트 위치로 이동
heap.pop_back(); // 마지막 요소 삭제
heapifyDown(0); // 루트부터 heapifyDown 호출로 힙 속성 복원
return root; // 추출한 최소값 반환
}
};
int main() {
MinHeap minHeap;
minHeap.insert(3);
minHeap.insert(1);
minHeap.insert(2);
cout << "직접 구현한 최소 힙에서 추출한 최소 값: " << minHeap.extractMin() << endl; // 출력: 1
return 0;
}