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

우선순위 큐(Priority Queue)

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

- 데이터를 우선순위에 따라 처리하고 싶을 때 사용

자료구조	추출되는 데이터
스택(Stack)	가장 나중에 삽입된 데이터
큐(Queue)	가장 먼저 삽입된 데이터
우선순위 큐(Priority Queue)	가장 우선순위가 높은 데이터

우선순위 큐(Priority Queue) 구현 방법

- 리스트 이용하여 구현

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

 

- 데이터의 개수가 N개일 때, 구현 방식에 따른 시간 복잡도

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

N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일 (힙 정렬) _ 시간 복잡도 : O(NlogN)

힙(Heap)

- 완전 이진 트리 자료구조

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

출처 : 이코테

- 루트 노드를 제거

- 최소 힙 (min heap) 

  루트 노드가 가장 작은 값을 가짐, 값이 가장 작은 데이터가 우선적으로 제거

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

- 최대 힙 (max heap)

  루트 노드가 가장 큰 값을 가짐, 값이 가장 큰 데이터가 우선적으로 제거

 

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