[ Python ] | heapq 사용법 | heapsort, 우선순위큐

1. 정의

complete binary tree

이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공

=> 원소들이 항상 정렬된 상태로 추가되고 삭제

2. 선언

import heapq

#다른 list를 heap으로 만든다
heapq.heapify(list)
#새로 선언
heap = []

heapq 모듈은 일반 list로 선언해도 heap으로 쓸 수 있다.

자바의 PriorityQueue 클래스처럼 리스트와 별개의 자료구조가 아닌 점에 유의해야함.

3. 기본 메소드

#원소추가
heapq.heappush(list, x) #(heap, 원소)

#원소삭제 -> 최소값 삭제(반환)
heapq.heappop(list)

#삭제하지않고 최소값 얻기
heap[0]

4. 활용

기본 제공되는 heapq는 Min heap이기 때문에 Max heap을 사용하려면 추가 작업이 필요

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []

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

while heap:
  print(heapq.heappop(heap)[1])  # index 1

출처 : https://www.daleseo.com/python-heapq/

[파이썬] heapq 모듈 사용법