[파이썬/python] 힙(Heap), Heapq 모듈

> 자료구조 힙(Heap)의 개념

https://mingchin.tistory.com/113

[자료구조/알고리즘] 이진 트리, 완전 이진 트리, 힙(Heap)

파이썬에서는 내장모듈인 heapq에서 구현된 것을 활용할 수 있다. 최댓값과 최솟값에 빠르게 접근하거나, 가장 작은 n개의 숫자 혹은 가장 큰 n개의 숫자 등을 구할 때 사용한다. 파이썬에서 제공하는 heapq는 기본적으로 최소 힙의 자료구조이다.

 

> heapq 모듈의 함수

import heapq as hq

# 일반 리스트를 힙 구조로 변환
hq.heapify(list)

# 힙 구조를 유자하면서, item을 heap 안에 추가
hq.heappush(heap, item)

# 힙 구조를 유지하면서, 가장 작은 항목을 팝하고 반환
hq.heappop(heap)

# pop하지 않고 가장 작은 항목에 액세스
heap[0]

# 힙에 item을 푸시하고, 가장 작은 항목을 pop하고 반환, heappush + heappop, 별도 실행보다 효율적
hq.heappushpop(heap, item)

# 힙에서 가장 작은 항목을 pop하고 반환, item 푸시, heappop + heappush, 별도 실행보다 효율적
hq.heapreplace(heap, item)

# n개의 가장 큰 요소의 리스트 반환, key로 비교 키 함수 지정 가능(iterable이 힙인 것이 좋음)
heapq.nlargest(n, iterable, key)

# n개의 가장 작은 요소의 리스트 반환, key로 비교 키 함수 지정 가능(iterable이 힙인 것이 좋음)
heapq.nsmallest(n, iterable, key)

> 최소 힙으로 최대 힙 구현하기

튜플을 활용한다. 아래와 같이 원래 숫자를 음수화하여 튜플의 앞쪽에 배치하면 원래 순서의 역순으로 정렬이 가능하고, heap은 별 다른 조건이 없으면 튜플의 앞 숫자를 기준으로 먼저 정렬함을 이용한 것이다. 가장 큰 값이 heap[0]임을 알 수 있다.

import heapq

nums = [5, 6, 2, 1, 7, 4, 10, 15]
heap = []

for num in nums:
    heapq.heappush(heap, (-num, num))  # (우선 순위, 값)
    
heap

> heapq를 활용한 문제

https://mingchin.tistory.com/114

[코딩 테스트 연습(파이썬/Python)] 프로그래머스 _ 힙(Heap) _ 더 맵게