Python의 heapq 모듈 활용하기

Python의 heapq 모듈은
리스트를 최소 힙(min-heap)으로 다룰 수 있게 해주는 유용한 도구
힙은 완전 이진 트리의 형태로,
부모 노드가 자식 노드보다 작은 성질을 가짐
이를 통해 최소값, 최대값을 효율적으로 관리할 수 있음

heapq의 주요 기능은 heappush, heappop, heapify, nlargest, nsmallest 등
heappush(heap, item)은 힙에 원소를 추가하고,
heappop(heap)은 최소값을 제거하여 반환
heapify(x)는 리스트를 힙 구조로 변환

K번째 최대 원소를 찾고 싶다면,
K개의 원소를 힙에 넣고
그 이후 원소는 비교하여 필요 시 pop하는 방식으로 구현할 수 있음
시간 복잡도는 O(n log k)로,
효율적인 데이터 처리 가능

heapq는 값이 같은 경우
먼저 들어간 순서대로 pop되는 특징이 있어, 안정성을 보장

import heapq

# heapq nlargest, nsmallest
nums = [3, 1, 4, 1, 5, 9, 2, 6]
print(heapq.nlargest(3, nums))  # 출력: [9, 6, 5]
print(heapq.nsmallest(3, nums))  # 출력: [1, 1, 2]

# 힙을 이용한 K번째 최대 원소 찾기
nums = [3, 1, 4, 1, 5, 9, 2, 6]
heap = []
k = 3
for num in nums:
    heapq.heappush(heap,num)
    if len(heap) > k:
        heapq.heappop(heap)
print(heapq.heappop(heap))

# 힙에서 가장 큰 원소 추출
nums = [3, 1, 4, 1, 5, 9, 2, 6]
heap = []
for num in nums:
    heapq.heappush(heap,-num)
print(-heapq.heappop(heap))

# 리스트를 힙으로 변환
nums = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(nums)
print(nums)

# heapq에서 가장 작은 원소 추출
nums = [3, 1, 4, 1, 5, 9, 2, 6]
heap = []
for num in nums:
    heapq.heappush(heap,num)
print(heapq.heappop(heap))

# 기본적인 heapq 사용
nums = [3,1,4,1,5,9,2,6]
heap = []
for num in nums:
    heapq.heappush(heap,num)
print(heap)