[Python] heapq 활용해 정렬 및 최소값 찾기

안녕하세요

오늘은 heapq 활용해서 더 빠르게 정렬하고 최소값을 찾아보도록 하겠습니다.

 

heapq는 “힙(Heap)” 자료구조를 구현한 파이썬 내장 모듈입니다.

힙(Heap)이란,

항상 부모 노드가 자식 노드보다 작거나(최소 힙)

항상 크거나(최대 힙) 인 완전이진트리 구조의 자료구조입니다.

 

파이썬의 heapq는 기본적으로 최소 힙(min-heap) 으로 동작합니다.
즉, “가장 작은 값이 항상 맨 앞에 위치”하도록 유지해줍니다.

 

또한 정렬과 비교를 해보면, 

정렬은 전체를 정리하지만, 힙은 "최소값만" 관리합니다.

 

정렬(sorted())은 모든 원소를 O(N log N) 시간에 정렬합니다.

하지만 “가장 작은 값 하나”만 필요한 경우라면,
힙은 O(log N) 만에 처리할 수 있습니다.

 

 

전체 코드입니다

import heapq

# 1. 리스트를 힙으로 변환
nums = [5, 1, 8, 3, 2]
heapq.heapify(nums)  # 리스트 → 힙 구조로 변환
print("힙 변환 후:", nums)  # 내부 구조는 정렬과 다름

# 2. 가장 작은 값 꺼내기 (자동으로 정렬된 구조 유지)
smallest = heapq.heappop(nums)
print("가장 작은 값 pop:", smallest)
print("pop 후 힙 상태:", nums)

# 3. 새 원소 추가
heapq.heappush(nums, 0)
print("0 추가 후 힙:", nums)

# 4. 여러 번 pop하면 오름차순으로 꺼낼 수 있음
sorted_nums = [heapq.heappop(nums) for _ in range(len(nums))]
print("정렬된 결과:", sorted_nums)

 

 

결과 입니다.