python: heapq모듈(최소 힙)

힙 자료구조

- 최소 힙: 부모 노드가 항상 자식보다 작거나 같은 값을 갖는 이진트리

- 최대 힙: 부모 노드가 항상 자식보다 크거나 같은 값을 갖는 이진트리

- 최댓값or최솟값을 빠르게 찾을 수 있음

- 요소 추가/삭제 시 데이터 자동정렬

 

- 루트 heap[0]은 항상 최소 값 저장

- 삭제(pop): 항상 루트 값을 삭제(최소값)

- 힙을 이용하여 오름차순/ 내림차순 정렬 가능(힙정렬)

 

 

heap모듈

- 최소 힙 자료구조(리스트 기반)

- 내장 모듈

 

 

<사용법>

import heapq

heap = []

기본 리스트를 생성해야함. (여기다가 넣고 뺄 거)

 

 

■ 원소 추가

heapq.heappush(heap, 2)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)

heappush: O(logN)

 

 

■ 원소 삭제

print(heapq.heappop(heap))

heappop: O(logN)

 

 

■ 최소값 얻기

print(heap[0])

항상 루트에는(인덱스 0) 최소값이 저장됨.

 

 

■ 기존 리스트를 힙으로 변환

heap = [4,1,7,3,8,5]
heapq.heapify(heap)

heapify: O(N)   // 리스트 재배치, 원소 하나하나 추가한 효과

 

 

■ 최대힙으로 활용

 

#1: 그냥 -를 취한 값을 넣어주어 최대값이 최소값이 되도록 만들기

heapq.heappush(heap, -2)
heapq.heappush(heap, -1)
heapq.heappush(heap, -3)

print(-heapq.heappop(heap))

 

#2

heapq.heappush(heap, (-1, 1))  # (우선순위, 값)
heapq.heappush(heap, (-2, 2))  # (우선순위, 값)
heapq.heappush(heap, (-3, 3))  # (우선순위, 값)

print(heapq.heappop(heap)[1])

우선순위 값을 설정해주면서 push

pop해서 값만 얻기(인덱스1)

 

 

 

참고자료: [Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기 (tistory.com)