#1927번 최소 힙

최소 힙(Min Heap) 이해와 파이썬 구현

최소 힙이란?

최소 힙은 완전 이진 트리를 기반으로 한 자료구조로, 각 노드의 값이 자식 노드의 값보다 작거나 같아야 하는 특성을 가집니다. 이로 인해 트리의 루트에는 항상 최소값이 위치하게 됩니다. 최소 힙은 다양한 알고리즘과 자료구조에서 중요하게 활용됩니다.

최소 힙의 기본 연산

• 삽입(Insertion): 새 요소를 힙의 마지막에 추가한 뒤, 부모 노드와 비교하며 힙의 조건을 만족시킬 위치로 조정합니다.
• 삭제(Deletion): 힙에서 요소를 제거할 때 주로 최소값(루트 노드)을 제거합니다. 루트 노드를 제거한 후 마지막 요소를 루트로 옮기고, 힙의 조건을 만족시키도록 재조정합니다.
• 최소값 찾기(Find Min): 루트 노드에 위치한 최소값을 즉각적으로 조회할 수 있습니다.

파이썬에서의 최소 힙 구현

파이썬의 heapq 모듈은 리스트를 최소 힙으로 다룰 수 있게 해주며, 힙 연산을 위한 다양한 함수를 제공합니다.

heapq 모듈 주요 함수

• heapq.heappush(heap, item): 항목을 힙에 추가합니다.
• heapq.heappop(heap): 힙에서 가장 작은 항목을 제거하고 반환합니다.
• heapq.heapify(x): 리스트 x를 즉각적으로 힙으로 변환합니다.

최소 힙 사용 예제

import heapq

# 빈 힙 생성
heap = []

# 힙에 요소 추가
heapq.heappush(heap, 10)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)

# 최소값 제거 및 반환
print(heapq.heappop(heap))  # 출력: 1

# 힙의 현재 상태 확인
print(heap)  # 출력: [5, 10]

# 리스트를 최소 힙으로 변환
list_to_heap = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(list_to_heap)
print(list_to_heap)  # 힙으로 변환된 리스트 출력

# 힙에서 n개의 가장 작은 요소 찾기
smallest = heapq.nsmallest(3, list_to_heap)
print(smallest)  # 출력: [1, 1, 2]

위 코드는 heapq 모듈을 활용해 최소 힙을 생성하고 관리하는 방법을 보여줍니다. 이를 통해 데이터의 최소값을 효율적으로 관리할 수 있으며, 우선순위 큐 구현 등에 활용될 수 있습니다.