힙과 우선순위 큐

이 포스트는 2021.12~2022.09 기간동안 벨로그에 작성한 글을 티스토리에 옮겨 적은 것입니다.

우선순위 큐
보통 큐는 가장 먼저 삽입된 데이터를 먼저 삭제하지만.. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다. 삽입/삭제의 시간복잡도는 logN 이다.

힙 자료구조
힙 자료구조는 우선순위 큐를 구현하기 위하여 사용하는 자료구조 중 하나다. 대부분의 프로그래밍 환경에서 우선순위 큐 라이브러리를 지원하기 때문에 직접 힙 자료구조를 작성해서 우선순위 큐를 구현할 일은 없다. 라이브러리 임포트 하는 방식만 잘 외워두자!

import heapq

사용 방법

import heapq

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

print(heapq.heappop(heap)) #10
print(heapq.heappop(heap)) #20
print(heapq.heappop(heap)) #50

heapq.heappush(큐 배열, 넣을 원소)와 heapq.heappop(큐 배열)을 기억하자.

참고자료: 이코테 240p