우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)

: 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

 

1) 리스트를 이용하여 구현

2) 힙(heap)을 이용하여 구현(단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일)

: 완전 이진 트리 자료구조

: 항상 루트노드를 제거한다

 

최소힙 - 루트노드가 가장 작은 값을 가진다 / 값이 작은 데이터가 우선적으로 제거

최대힙 - 루트노드가 가장 큰 값을 가진다 / 값이 큰 데이터가 우선적으로 제거

 

* 완전 이진 트리

: 루트 노드부터 시작하여 왼쪽 자식노드, 오른쪽 자식노드 순서대로데이터가 차례로 삽입되는 트리

 

* 최소 힙 구성 함수

: 부모 노드로 거슬러 올라가며, 부모다 값이 더 작은 경우에 위치를 교체

 

Python

import sys
import heapq #기본은 최소힙이다.

input = sys.stdin.readline

def heapsort(iterable):
	h = []
    result = []
    #모든 원소를 차례대로 힙에 삽입
    for value in iterable:
    	heapq.heappush(h, value)
    #힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i 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])