파이썬_기초 35_heapq

heapq

 

heapq 모듈은 힙큐 알고리즘 구현을 해줍니다.

heapq 모듈은 이진 트리의 최소힙 자료구조를 제공합니다.

 

heapq에서는 모든 k에 대해 heap[k] <= heap[2*k+1]과 heap[k] <= heap[2*k+2]을 만족하는 배열을 사용합니다.

 

따라서 인덱스 0인 이진 트리의 루트에 가장 작은 요소가 있습니다.

 

heapq.heappush(heap 이름, 추가할 원소)
heapq.heappop(heap 이름)
heapq.heappushpop(heap 이름, 추가할 원소)
heapq.heapify(리스트 이름)

heapq의 기본 함수입니다.

 

heappush는 힙에 원소를 추가합니다.
heappop은 가장 작은 원소를 삭제합니다.
heappushpop은 힙에 원소를 추가하고 가장 작은 원소를 삭제합니다. 이는 heappush()한 다음 heappop()을 각각 사용하는 것보다 더 유용합니다.

heapify는 리스트를 인자로 넘기면 리스트 원소들을 힙 구조에 맞게 바꿔줍니다. 새로운 리스트를 생성한 후 heappush() 함수로 원소를 하나씩 추가하는 것을 한번에 해주는 기능입니다.

 

import heapq

a=[]

heapq.heappush(a, 1)
heapq.heappush(a, 5)
heapq.heappush(a, 3)
heapq.heappush(a, 2)
heapq.heappush(a, 4)

# 출력>>[1, 2, 3, 5, 4]
print(a)

# 출력>>1
print(heapq.heappop(a))

b=[8,6,4,3,1,5]

heapq.heapify(b)

# 출력>>[1, 3, 4, 8, 6, 5]
print(b)