[개발 일기] 2025.02.14 - 우선순위 큐

💡 개요

오늘은 코딩테스트 문제를 풀 때 자주 사용되는 우선순위 큐에 대해 정리해 보자.

 

 

 

📕 우선순위 큐

우선순위 큐란 Queue 인터페이스의 구현체로, Queue의 특징인 선입선출 방식이 아니라, 우선순위 큐에 설정된 우선순위가 높은 요소가 먼저 나오는 방식으로 동작하는 자료구조이다.

 

 

다양한 방법으로 구현 가능한데, 주로 힙(Heap)을 사용한다.

 

 

 

🚀 최소 힙

 

최소 힙은 부모 노드가 자식 노드보다 작은 자료구조를 말한다.

 

 

그렇기 때문에 최소 힙의 루트 노드는 힙에 있는 노드 중에서 가장 작은 값이다.

 

 

 

🚀 최대 힙

 

최대 힙은 부모 노드가 자식 노드보다 큰 자료구조를 말한다.

 

 

그렇기 때문에 최대 힙의 루트 노드는 힙에 있는 노드 중에서 가장 큰 값이다.

 

 

 

🚀 우선순위 큐와 최대 힙, 최소 힙

 

보다시피 최대 힙의 루트 노드는 트리 상의 노드 중에서 가장 큰 값, 최소 힙의 루트 노드는 트리 상의 노드 중에서 가장 작은 값을 나타낸다.

 

 

우선순위 큐에서 이를 활용하면 다음과 같이 사용할 수 있다.

 

• 값이 작은 요소가 우선적으로 처리될 경우 → 최소 힙 사용
• 값이 큰 요소가 우선적으로 처리될 경우 → 최대 힙 사용

 

그리고 최대 힙, 최소 힙 모두 완전 이진트리 형태이기 때문에 삽입, 삭제에 연산에 발생하는 시간 복잡도는 O(logN) 이다.

 

 

하지만 탐색 연산에선 힙은 정렬되지 않은 형태이기 때문에 O(N)의 시간복잡도가 발생한다.