[자료구조] 우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)

들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조

 

사용 용도

물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야하는 경우

 

특징

힙(heap)을 이용한 구현 방법

루트 노드엔 우선순위가 높은 값이 들어간다.

힙에서는 항상 루트 노드를 제거한다.

힙은 완전 이진 트리 형태로 구성되어있다.

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

n = int(input())
heap = []

for i in range(n, 0, -1):
    heappush(heap, i)
print('-' * 15, 'heappop', '-' * 15)
for i in range(n):
    print(heappop(heap))

# 5
# --------------- heappop ---------------
# 1
# 2
# 3
# 4
# 5