우선순위 큐(Priority Queue)가 뭔데 !

https://www.youtube.com/watch?v=AjFlp951nz0 

우선순위 큐 (Priority Queue)

• 우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
• 큐를 구현 하는 방법
  1. 리스트를 이용하여 구현 - 삽입: $O(1)$, 삭제: $O(N)$
  2. 힙(heap)을 이용하여 구현 - 삽입: $O(logN)$, 삭제: $O(logN)$

Heap으로 구현하자..

• N개의 데이터를 모두 힙에 넣었다가 꺼내면: $O(NlogN)$

 

힙(Heap)이 뭔데..

• 힙은 완전 이진 트리 자료구조의 일종
• 힙에서는 항상 루트 노드(root node)를 제거

최소 힙 (Min heap)

• 루트 노드가  가장 작은 값을 가짐
• 값이 작은 데이터를 우선적으로 pop !(제거)

최대 힙 (Max heap)

• 루트 노드가 가장 큰 값을 가짐
• 값이 큰 데이터를 우선적으로 pop !(제거)

+) 완전 이진 트리 (Complete BInary Tree)

• 루트 노드부터 시작하여, 왼쪽, 오른쪽 자식노드 순서대로 데이터가 삽입됨

최소 힙 구성 함수: Min-Heapify()

(상향식) 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체

 

CODE

우선순위 큐 라이브러리를 활용합 힙 정렬 구현 예제

import sys
import heapq

def heatsort(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 = heatsort(arr)
for i in range(n):
    print(res[i])