[Python] min-hip을 이용한 Priority Queue

- 최소 힙(min-heap)의 구조

- 삽입/삭제: O(logN)

import heapq로 사용 가능

push: heapq.heappush(hq, item)

pop: heapq.heappop(hq)

      

      

      

    
    

      <python />
    
import heapq
pq = []
heapq.heappush(pq, 6)
heapq.heappush(pq, 12)
heapq.heappop(pq)

 

heapify

- 리스트 x를 heap으로 변환

      

      

      

    
    

      <python />
    
x = [4, 3, 1, 2, 5, 6]
print(x) # [4, 3, 1, 2, 5, 6]
heapq.heapify(x)
print(x) # [1, 2, 4, 3, 5, 6]

 

1. heapq를 사용하는 이유?

from queue import PriorityQueue로 일반 우선순위 큐도 사용할 수 있다.

하지만 이는 멀티스레드 환경에서 사용해도 문제가 없도록 thread-safe 하게 설계되어 있다 -> 느리다

코테에서는 멀티스레딩 프로그램을 쓰지 않는 경우가 대부분이기 때문에 코테용으로 쓸 떄는 그냥 heapq를 쓰자..!

 

 

참고 예제: BOJ 11286: 절댓값 힙

2022.04.22 - [ALGORITHM/BOJ] - 11286- 절댓값 힙

11286- 절댓값 힙