우선순위 큐 (Priority Queue)

1. 우선순위 큐 (Priority Queue) 우선순위 큐는 일반적인 큐(선입선출, First In. First Out)와 다르게 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조입니다. 여러 데이터 중 가장 우선순위가 높은 데이터에 대한 빠른 갱신과 접근이 가능할 때 사용합니다. 일반적으로 Heap 구조로 구현하며, 배열과 연결리스트로도 구현이 가능합니다. 배열과 연결 리스트는 간단히 구현이 가능하지만 데이터 삽입의 경우 모든 인덱스를 탐색해야하는 최악의 경우 선능이 좋지 않을 수 있으며, Heap은 구현은 배열과 연결리스트에 비해 어렵지만 좋은 선능을 가집니다. 배열, 연결리스트의 시간복잡도 [ 삽입 : O(n) , 삭제 : O(1) ] Heap의 시간복잡도 [ ..
Algorithm 2022. 6. 13. 18:10
1