[이코테]우선순위 큐

Coding Test 11

이코테 11

1. 우선순위 큐

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

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

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

---

• 우선순위 큐 구현 방법

1. 리스트
2. 힙(heap)

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

---

2. 힙(Heap)

• 완전 이진 트리 자료구조 (마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 구조)
• 항상 루트 노드를 제거

---

• 최소 힙 : 루트 노드가 가장 작은 값 -> 작은 데이터 우선 제거
• 최대 힙 : 루트 노드가 가장 큰 값 -> 큰 데이터 우선 제거

---

• 추가 : 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체(최소 힙)
• 제거 : 가장 마지막 노드가 루트 노드의 위치에 오도록 함

import heapq #최소힙이 기본값

def heapsort(iterable):
  h = []
  result = []
  for v in iterable :
    heapq.heappush(h, v) #추가

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