본 포스팅은 (이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬을 참고하여 공부하고 정리한 글임을 밝힙니다.

---

우선순위 큐(Priority Queue)

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

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

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

• 우선순위 큐 구현 방법
  (1) 단순히 리스트를 이용하여 구현
  (2) 힙(heap)을 이용하여 구현

• 데이터 개수가 N개 일 때, 구현 방식에 따라서 시간 복잡도를 비교한 내용

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

• 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일 (힙 정렬)

  • 시간 복잡도 $O(NlogN)$

힙(Heap)의 특징

완전 이진 트리(Complete Binary Tree)

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

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

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

힙에 새로운 원소 삽입될 때

• 새로운 원소가 삽입되었을 때 $O(logN)$의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다

힙에서 원소가 제거될 때

• $O(logN)$의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다

  • 원소 제거될 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 한다
    
  • 이후에 루트 노드에서부터 하향식으로(더 작은 자식 노드로) 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])