우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)

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

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

2) 힙(heap)을 이용하여 구현(단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일)

: 완전 이진 트리 자료구조

: 항상 루트노드를 제거한다

최소힙 - 루트노드가 가장 작은 값을 가진다 / 값이 작은 데이터가 우선적으로 제거

최대힙 - 루트노드가 가장 큰 값을 가진다 / 값이 큰 데이터가 우선적으로 제거

* 완전 이진 트리

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

* 최소 힙 구성 함수

: 부모 노드로 거슬러 올라가며, 부모다 값이 더 작은 경우에 위치를 교체

Python

import sys import heapq #기본은 최소힙이다. input = sys.stdin.readline def heapsort(iterable): h = [] result = [] #모든 원소를 차례대로 힙에 삽입 for value in iterable: heapq.heappush(h, value) #힙에 삽입된 모든 원소를 차례대로 꺼내어 담기 for i 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])

from http://404canfind.tistory.com/30 by ccl(A) rewrite - 2021-10-11 14:26:39