힙(heap)은 특정한 규칙에 따라 정렬된 완전 이진 트리(Complete Binary Tree)를 기반으로 하는 자료구조입니다.힙은 주로 우선순위 큐(priority queue)를 구현하는 데 사용되며, 다양한 우선순위에 따라 데이터를 정렬하고 효율적으로 관리할 수 있도록 도와줍니다.
1. 힙의 특징
힙은 크게 두 종류로 나뉩니다:
- 최소 힙(Min Heap): 힙 내의 모든 노드의 부모 노드는 자식 노드보다 작거나 같은 값을 가집니다. 루트 노드가 최솟값을 가지게 됩니다.
- 최대 힙(Max Heap): 힙 내의 모든 노드의 부모 노드는 자식 노드보다 크거나 같은 값을 가집니다. 루트 노드가 최댓값을 가지게 됩니다.
힙은 다음과 같은 특징을 가지고 있습니다:
- 삽입과 삭제가 빠르다: 최상위 노드(루트)에 접근하는 것이 빠르므로 최소값 또는 최댓값을 찾거나, 새로운 값을 삽입하거나 삭제하는데 효율적입니다.
- 이진 트리 형태를 유지한다: 완전 이진 트리의 형태를 유지하면서 노드들이 저장됩니다.
2. 힙 정렬 구현
Python
def heapify(arr, n, i):
largest = i # 가장 큰 값은 현재 노드로 설정
left_child = 2 * i + 1
right_child = 2 * i + 2
# 왼쪽 자식이 부모보다 크다면 인덱스 업데이트
if left_child < n and arr[left_child] > arr[largest]:
largest = left_child
# 오른쪽 자식이 부모보다 크다면 인덱스 업데이트
if right_child < n and arr[right_child] > arr[largest]:
largest = right_child
# 최대값이 자식 노드로 이동한 경우 교환
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
# 변경된 노드에서 재귀적으로 heapify 호출
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# 최대 heap 구성
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 정렬 수행
for i in range(n - 1, 0, -1):
# 루트 노드(최대값)와 마지막 노드 교환
arr[i], arr[0] = arr[0], arr[i]
# 변경된 heap에서 다시 최대 heap 구성
heapify(arr, i, 0)
# 테스트
arr = [12, 11, 13, 5, 6, 7]
print("정렬 전 배열:", arr)
heap_sort(arr)
print("정렬 후 배열:", arr)
#정렬 후 배열: [5, 6, 7, 11, 12, 13]3. heapq 모듈 사용법
3.1. heapq.heappush(heap, item)
리스트 heap에 요소 item을 추가하고, heap 속성을 유지합니다.
Python
import heapq
heap = [3, 1, 5, 2, 7]
heapq.heappush(heap, 4)
print(heap) # 출력: [1, 2, 3, 4, 7, 5]3.2. heapq.heappop(heap)
리스트 heap에서 최소값(최상위 노드)을 추출하고 반환하며, heap 속성을 유지합니다.
Python
import heapq
heap = [1, 2, 3, 4, 7, 5]
min_value = heapq.heappop(heap)
print(min_value) # 출력: 1
print(heap) # 출력: [2, 4, 3, 5, 7]3.3. heapq.heapify(x)
리스트 x를 heap 으로 변환하여 heap 속성을 유지합니다.
Python
import heapq
heap = [3, 1, 5, 2, 7]
heapq.heapify(heap)
print(heap) # 출력: [1, 2, 5, 3, 7]3.4. heapq.nlargest(n, iterable[, key])와 heapq.nsmallest(n, iterable[, key])
Python
import heapq
nums = [3, 1, 5, 2, 7]
largest_two = heapq.nlargest(2, nums)
smallest_two = heapq.nsmallest(2, nums)
print(largest_two) # 출력: [7, 5]
print(smallest_two) # 출력: [1, 2]편안한 코딩하세요