우선순위 큐와 힙

나동빈 이코테 유튜브 강의 정리

https://www.youtube.com/watch?v=AjFlp951nz0&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=11 

 

 

우선순위 큐(Priority Queue)

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

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

 

예시) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우

스택 - 가장 나중에 삽입된 데이터

큐 - 가장 먼저 삽입된 데이터

우선순위 큐 - 가장 우선순위가 높은 데이터

 

 

우선순위 큐 구현 방법

- 리스트 이용

리스트에 차례대로 뒷쪽에 연달아 넣은 후,

데이터를 꺼낼 때는 리스트에서 각각의 데이터 확인한 뒤에 가장 값이 큰 데이터를 뽑아서 추출

- 힙 자료구조를 이용

 

 

시간복잡도

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

시간복잡도는 O(NlogN)

 

 

힙(Heap)의 특징

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

최소 힙(min heap)

루트 노드가 가장 작은 값을 가진다

따라서 값이 가장 작은 데이터가 우선적으로 제거된다

최대 힙(max heap)

루트 노드가 가장 큰 값을 가진다

따라서 값이 큰 데이터가 우선적으로 제거된다

 

 

완전 이진 트리 (Complete Binary Tree)

루트(root) 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리(tree)

 

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

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

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

 

 

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(heapa.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])