우선순위 큐(Priority Queue)

 

안녕하세요! 공대남입니다.

오늘은 우선순위 큐(Priority Queue)에 대해 알아보겠습니다.

 

Queue는 먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 특징을 가진 선형 자료구조입니다.
우선순위 큐(Priority Queue) 또한 큐와 비슷하지만 다른 점은 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조입니다.

=> 우선순위 큐는 array의 항상 마지막 값이 최대값을 항상 보장하지는 않기 때문에 arr.sort()를 하거나 min, max함수를 이용해 최대,최소값을 구하면 된다

 

import sys
import heapq
input = sys.stdin.readline

def heapsort(iterable):
	h = []
	result = []
    for value in iterable:
    	heapq.heappush(h, value)
    for i in range(len(h)):
    	result.append(heapq.heappop(h))
    return result
    
n = int(input())
arr = []

for i in range(n):
	arr.append(int(input()))

res = heapsort(arr)

for i in range(n):
	print(res[i])