[Data Structure] 우선순위 Queue

[2d3k]

동작방식?

[2d3k]

우선순위 큐(Priority Queue)는 각각의 요소들이 우선순위를 가지고 있으며, 우선순위가 높은 요소가 먼저 처리되는 자료구조입니다. 이러한 동작 방식은 일반적인 큐와는 다르게, 데이터를 삽입하거나 삭제할 때 우선순위를 고려하여 처리됩니다.

일반적으로 우선순위 큐는 힙(Heap) 자료구조를 이용하여 구현됩니다. 힙은 부모 노드와 자식 노드 간의 관계를 이용하여 구현되며, 일반적으로는 최소 힙(Min Heap) 또는 최대 힙(Max Heap)으로 구현됩니다.

최소 힙은 부모 노드의 값이 자식 노드의 값보다 작은 경우, 루트 노드부터 시작하여 하위 노드로 내려가면서 최소값을 가진 노드를 찾아 반환합니다. 최대 힙은 최소 힙과 반대로 부모 노드의 값이 자식 노드의 값보다 큰 경우, 루트 노드부터 시작하여 하위 노드로 내려가면서 최대값을 가진 노드를 찾아 반환합니다.

우선순위 큐는 일반적으로 다음과 같은 두 가지 연산이 가능합니다.

삽입 연산(Insertion Operation): 새로운 요소를 우선순위 큐에 추가합니다. 이때 삽입되는 요소는 우선순위에 따라 위치가 결정됩니다.

삭제 연산(Deletion Operation): 우선순위가 가장 높은 요소를 우선순위 큐에서 제거합니다. 이때 가장 높은 우선순위를 가진 요소는 루트 노드에 위치하므로, 루트 노드를 제거하고 다시 힙을 구성하여 다음으로 높은 우선순위의 요소를 반환합니다.

이러한 방식으로 우선순위 큐는 다양한 문제에 적용될 수 있으며, 우선순위가 높은 작업이 먼저 처리되어야 하는 시스템에서 효과적으로 사용됩니다.

[hyeonayou]

1. 일반적인 큐(Queue)는 먼저 집어넣은 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장하는 선형 자료구조입니다. 하지만 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말합니다.

우선순위 큐는 다음과 같은 속성을 가지고 있습니다.

1) 모든 항목에는 우선순위가 있습니다. 2) 우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 queue에서 제외됩니다. 3) 두 요소의 우선 순위가 같으면 queue의 순서에 따라 제공됩니다 4) 운영체제의 작업 스케줄링, 정렬, 네트워크 관리 등의 다양한 기술에 적용되고 있습니다.

[] 우선순위 큐는 완전 이진트리 형태의 힙을 이용해 구현할 수 있습니다. 우선순위 큐의 삽입과 삭제는 𝑂(𝑙𝑜𝑔𝑁)의 시간 복잡도를 가집니다 따라서 우선순위 큐를 이용한 정렬은 𝑂(𝑁𝑙𝑜𝑔𝑁)의 시간 복잡도를 가집니다.