Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- binary search
- mock service worker
- 분산 네트워크
- BFS
- 너비우선탐색
- await
- Eratosthenes
- var
- 이진탐색
- MVC패턴
- https
- deque
- 유클리드 호제법
- 이분탐색
- 알고리즘
- 탐욕 알고리즘
- 큐
- 에라토스테네스
- content delivery network
- 깊이 우선 탐색
- 우선순위큐
- 모킹
- painting
- greedy
- async
- sieve
- 탐욕법
- CSSOM
- 그리디 알고리즘
- MSW
Archives
- Today
- Total
갱주
힙 (Heap) 본문
힙은 우선순위 큐를 위해 만들어진 자료구조다.
🧐우선순위 큐 (Priority Queue)
- 우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.
📌Heap이란?
Heap은 기본적으로 최대 힙 (Max Heap)과 최소 힙 (Min Heap)으로 나눌 수 있습니다.
- 최대 힙 (Max Heap): 부모 노드는 자식 노드들보다 크거나 같은 값을 가집니다. 즉, 루트 노드에는 가장 큰 값이 위치합니다.
- 최소 힙 (Min Heap): 부모 노드는 자식 노드들보다 작거나 같은 값을 가집니다. 즉, 루트 노드에는 가장 작은 값이 위치합니다.
❗Heap의 특징
- 완전 이진 트리: Heap은 노드들이 왼쪽에서 오른쪽으로 빈틈없이 채워지는 완전 이진 트리 구조를 가집니다.
- 효율적인 연산: 힙에서는 삽입, 삭제 등의 연산이 발생할 때도 트리 구조를 유지하는데, 이를 위해 시간 복잡도 O(log n) 내에서 연산을 수행합니다.
- 빠른 최대/최소 값 탐색: 트리의 루트에 항상 최대값(최대 힙)이나 최소값(최소 힙)이 존재하므로, 이러한 값들을 빠르게 탐색할 수 있습니다.
💻Heap의 주요 연산
- 삽입 (Insert): 새로 삽입된 요소는 완전 이진 트리의 특성상 트리의 마지막 노드에 추가됩니다. 이후 부모 노드와 비교하며 자리를 교환하는 방식으로 힙의 조건을 만족시킵니다.
- 삭제 (Delete): 루트 노드(최대값 혹은 최소값)를 삭제한 후, 트리의 마지막 노드를 루트 자리에 옮깁니다. 이후 자식 노드들과 비교하며 자리를 교환하여 힙의 구조를 다시 정렬합니다.
- 힙 정렬 (Heap Sort): 힙을 이용하면 배열을 정렬할 수 있습니다. 힙을 통해 최대값 또는 최소값을 지속적으로 추출하고, 추출된 값을 배열에 넣어 정렬을 수행합니다. 이 과정의 시간 복잡도는 O(n log n)입니다.
🛠️구현 예시
Python에서는 heapq 모듈을 제공하여 간단하게 최소 힙을 구현할 수 있습니다.
- 최소힙 현
import heapq
# 최소 힙 생성
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 5)
print("Min Heap:", min_heap) # [1, 3, 5]
# 최소값을 추출 (삭제)
min_value = heapq.heappop(min_heap)
print("Heap after pop:", min_heap) # [3, 5]
- 최대힙 구현
Python의 heapq 모듈은 기본적으로 최소 힙을 지원하므로, 최대 힙을 구현하려면 음수 값을 넣어주는 방식으로 처리합니다. 힙에 값을 넣을 때 음수로 변환하고, 꺼낼 때 다시 양수로 변환하는 방식입니다.
# 최대 힙 생성 (음수 값을 이용하여 최대 힙으로 구현)
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -5)
print("Max Heap (using negatives):", max_heap) # [-5, -1, -3]
# 최대값을 추출 (삭제)
max_value = -heapq.heappop(max_heap)
print("Heap after pop:", [-x for x in max_heap]) # [3, 1]
활용 예시
- 우선순위 작업 처리: 긴급한 작업이 먼저 처리되는 환경에서는 최대 힙이나 최소 힙을 사용하여 높은 우선순위를 가진 작업을 빠르게 처리할 수 있습니다.
- 알고리즘 최적화: 다익스트라와 같은 그래프 알고리즘에서 최소 비용 경로를 빠르게 찾는 데 사용됩니다.
'자료구조' 카테고리의 다른 글
스택(Stack)과 큐(Queue) (1) | 2024.10.14 |
---|