개요
📌 HEAPQ
힙 큐 알고리즘
-
heap: 데이터의 집합에서 최댓값이나 최솟값을 빠르게 찾기 위해 고안된 자료구조 -
완전 이진 트리의 한 형태로, 각 노드의 값이 해당 노드의 자식 노드들보다 우선순위가 높거나 낮은 조건을 만족하는 특징을 가지고 있음.
📌 유형
-
최소 힙 (Min Heap): 각 부모 노드의 값이 자식 노드의 값보다 작거나 같다.
따라서 힙의 루트에는 항상 가장 작은 값이 위치 -
최대 힙 (Max Heap): 각 부모 노드의 값이 자식 노드의 값보다 크거나 같다.
여기서는 힙의 루트에 가장 큰 값이 위치
-
힙을 사용하는 주된 이유는
우선순위 큐 (Priority Queue)를 구현하기 위함. -
우선순위 큐는 요소들이 우선순위에 따라 정렬되어 있으며,
가장 높은 우선순위를 가진 요소를 빠르게 추출할 수 있어야 하는데,
힙 구조는 이러한 조건을 만족시키는 데 매우 효율적이다.
📌 모듈
heapq모듈은 Python의 표준 라이브러리에 포함되어 있다.
파이썬의heapq모듈은 최소 힙을 구현하고 있으며, 아래와 같은 함수들을 제공
-
heapq.heappush(heap, item): 힙에 새로운 요소를 추가하면서 힙 속성을 유지 -
heapq.heappop(heap): 힙에서 가장 작은 요소를 제거하고 그 값을 반환 -
heapq.heappushpop(heap, item): 힙에 새 요소를 추가한 다음, 가장 작은 요소를 제거하고 반환.
heappush를 호출한 후 heappop을 호출하는 것보다 더 효율적으로 실행된다. -
heapq.heapify(x): 주어진 리스트를 즉시 최소 힙으로 변환 -
heapq.heapreplace(heap, item): 힙에서 가장 작은 요소를 제거하고 새로운 요소를 추가 -
heapq.nlargest(k, iterable): 주어진 반복 가능한 데이터에서 가장 큰 k개의 요소 반환 -
heapq.nsmallest(k, iterable): 주어진 반복 가능한 데이터에서 가장 작은 k개의 요소 반환
- 이 함수들은 데이터를 효율적으로 관리하고 처리하는 데 유용하며,
특히 동적 우선순위 큐를 구현할 때 자주 사용된다.
