📌 우선순위 큐(Priority Queue)란?
우선순위 큐는 데이터들이 우선순위에 따라 처리되는 자료구조를 말합니다.
일반적으로 가장 높은 우선순위를 가진 요소가 가장 먼저 처리되며, 만약 우선순위가 같은 경우에도 입력 순서에 따라 처리될 수 있습니다.
우선순위 큐는 보통 힙(Heap) 자료구조를 이용하여 구현됩니다. 우선순위 큐에서 배열 대신 힙(Heap) 자료구조를 사용하는 이유는 효율성과 성능 때문입니다. 힙은 완전 이진 트리의 형태를 가지며, 부모 노드의 우선순위가 자식 노드의 우선순위보다 항상 높은 특징을 갖습니다. 더 자세한 내용은 아래에서 다루도록 하겠습니다.
우선순위 큐는 주로 아래의 예시들에서 사용됩니다.
작업 스케줄링: 우선순위가 높은 작업을 먼저 처리하는 스케줄링에 사용됩니다.
이벤트 처리: 이벤트의 발생 순서나 중요도에 따라 처리해야 할 때 사용됩니다.
최단 경로 알고리즘: 다익스트라(Dijkstra) 알고리즘 등 최단 경로를 구하는 알고리즘에서 우선순위 큐를 활용합니다.
✏️ 주요 동작
삽입(Insertion): 우선순위 큐에 요소를 삽입합니다. 이때, 요소는 우선순위에 맞추어 위치가 결정됩니다.
삭제(Deletion): 우선순위가 가장 높은 요소를 삭제합니다. 가장 높은 우선순위 요소는 우선순위 큐의 특성에 따라 힙의 루트 노드에 위치하게 됩니다.
탐색(Peek): 우선순위가 가장 높은 요소를 확인합니다. 이때, 요소는 삭제되지 않습니다.
📌 힙(Heap)이란?
힙(Heap)은 완전 이진 트리(Complete Binary Tree)의 일종으로, 부모 노드와 자식 노드 간의 우선순위 관계를 가지는 자료구조입니다.
힙은 완전 이진 트리의 형태를 가지며, 부모 노드의 우선순위가 자식 노드의 우선순위보다 항상 높은 특징을 갖습니다. 이러한 특성 때문에 우선순위 큐에 요소를 삽입하거나 삭제할 때, 배열 대신 힙을 사용하면 효율적인 연산이 가능합니다. 삽입과 삭제 연산의 시간 복잡도는 O(log n)으로 효율적입니다.
우선순위 큐에서는 가장 높은 우선순위 요소에 빠르게 접근해야 합니다. 힙은 루트 노드에 항상 최소값 혹은 최대값이 위치하도록 유지되므로, 상수 시간(O(1)) 내에 최소 혹은 최대값에 접근할 수 있습니다. 이는 배열을 사용하는 경우보다 효율적인 탐색을 가능하게 합니다.
힙은 동적 크기 조절이 가능한 자료구조로, 요소의 삽입이나 삭제에 따라 힙의 크기를 조정할 수 있습니다. 배열의 경우에는 크기를 미리 정해놓아야 하거나 크기를 조정하기 위해 별도의 작업이 필요하지만, 힙은 자체적으로 크기를 유동적으로 조절할 수 있어 효율적인 공간 관리를 가능하게 합니다.
✏️ 주요 동작
삽입(Insertion)
삽입 연산은 일반적으로 힙의 마지막 노드에 새로운 요소를 추가하는 과정입니다. 새로운 요소를 힙의 맨 끝에 추가한 뒤, 부모 노드와 비교하여 우선순위에 맞는 위치를 찾아갑니다. 부모 노드의 우선순위보다 새로운 요소의 우선순위가 높다면 부모 노드와 위치를 바꿔주는 작업을 반복합니다. 이 과정을 요소가 올바른 위치에 도달할 때까지 반복하여 요소를 삽입합니다. 시간 복잡도는 일반적으로 O(log n)입니다.
삭제(Deletion)
삭제 연산은 힙에서 우선순위가 가장 높은 루트 노드를 제거하는 과정입니다. 루트 노드를 삭제한 뒤, 힙의 마지막 노드를 루트로 이동시킵니다. 이후 자식 노드들과 우선순위를 비교하면서 자식 노드 중 우선순위가 높은 노드와 위치를 바꿔주는 작업을 반복합니다. 이 과정을 우선순위가 올바른 위치에 도달할 때까지 반복하여 요소를 삭제합니다. 시간 복잡도는 일반적으로 O(log n)입니다.
피드백 및 개선점은 댓글을 통해 알려주세요😊
