[Data Structure] 1. 우선순위 큐(Priority Queue) & 힙(Heap)

우선순위 큐(Priority Queue) 우선순위 큐(Priority Queue)는 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 우선순위 큐의 요소는 모두 우선순위를 가지고 있으며, 우선순위가 같은 경우에는 큐의 순서에 따라 처리한다. 우선순위 큐는 여러 방식으로 구현할 수 있지만 힙(heap)이 가장 효율을 보이기 때문에 일반적으로 힙을 이용하여 구현한다. 방식 시간 복잡도 배열 O(N) 연결 리스트 O(N) 힙 O(logN) 힙(heap) 힙의 특징 완전이진트리 형태로 이루어져 있다. 부모노드는 자식노드 사이에 대소관계를 가지고 있다. 중복된 키를 허용한다. 힙의 종류 최대 힙(max heap): 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 힙 최소 힙(min heap): ..

원문링크 : [Data Structure] 1. 우선순위 큐(Priority Queue) & 힙(Heap)