[python] heapq(힙큐, 우선순위큐)

📗heapq란?

간단하게 리스트내에서 가장 작은 값이 맨처음위치(인덱스 0)애 오게 해주는 내장 모듈

우선순위 큐라고 알면 쉽다.

 

🔵 시작하기

import heapq

 

🔵 선언하기

보통 리스트를 선언하는 것처럼 만든다.

heap_list = []

 

🔵 원소 추가하기 ( heapq.heappush(리스트, 값 ))

- 아래 보이는 것 처럼 가장 작은 값이 맨 처음 위치에 왔다.

시간복잡도 O(logn)

heapq.heappush(heap_list, 5)
heapq.heappush(heap_list, 10)
heapq.heappush(heap_list, 99)
heapq.heappush(heap_list, 2)

print(heap_list) # [2, 5, 99, 10]

 

🔵 원소 삭제하기 ( heapq.heappop(리스트) )

- 제일 처음에 있는 값이 삭제되면서 그 값을 리턴한다. 값을 삭제하고 다시 출력해보니 힙이 정렬 되어 있다. 

시간복잡도 O(logn)

print(heapq.heappop(heap_list))  # [2, 5, 99, 10]
print(heap_list)  # [5, 10, 99] 
a = heapq.heappop(heap_list)
print(a)  # 5

 

🔵 기존의 리스트를 힙으로 변환하기 ( heapq.heapify(리스트) )

시간복잡도 O(n)

ano_list = [9, 8, 7, 6, 5, 4, 1, 2, 5]
heapq.heapify(ano_list)
print(ano_list)  # [1, 2, 4, 5, 5, 9, 7, 6, 8]

 

🔵 최대값 구하기! (응용)

- 값들을 튜플 형태로 넣어준다. 튜플형태로 넣어주면 튜플의 0번째 인덱스를 기준으로 힙정렬이 된다.

numbers = [1,5,9,3,7,6,4,2,8]
max_list = []
for number in numbers:
    heapq.heappush(max_list, (-number, number)) # ( 우선순위, -를 붙이면 가장 큰 값이 가장 작아진다. 실제 값)

while max_list:
    print(heapq.heappop(max_list)[1])