우선순위 큐 (Priority Queue)

우선순위 큐란?

• 우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
• 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용함.

 

구현 하는 방법 

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

2) 힙(heap)을 이용하여 구현

 

우선 순위 큐 구현 방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙(Heap)	O(logN)	O(logN)

 

• 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다.
  • 이 경우 시간 복잡도는 O(NlogN)

 

힙(Heap)의 특징

• 힙은 완전 이진 트리 자료구조의 일종이다.
• 힙에서는 항상 루트 노드(root node)를 제거한다.
• 최소 힙(min heap)
  • 루트 노드가 가장 작은 값을 가진다
  • 따라서 값이 작은 데이터가 우선적으로 제거된다.
• 최대 힙(max heap)
  • 루트 노드가 가장 큰 값을 가진다.
  • 따라서 값이 큰 데이터가 우선적으로 제거된다. 

완전 이진 트리 (Complete Binary Tree)

• 완전 이진 트리란 루트 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리를 의미함.

 

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

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

 

 

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

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])