-
우선순위 큐와 힙은 서로 밀접하게 관련된 자료 구조다. 우선순위 큐는 추상적인 개념으로서 다양한 방식으로 구현될 수 있으며, 힙은 그 중에서도 매우 효율적인 구현 방식 중 하나다.
우선순위 큐(Priority Queue)
우선순위 큐는 각 요소가 우선순위를 가지며, 높은 우선순위를 가진 요소가 낮은 우선순위를 가진 요소보다 먼저 처리되는 자료 구조다. 이를 통해 데이터가 삽입되는 순서와 상관없이 항상 가장 높은 우선순위를 가진 요소를 효율적으로 찾아낼 수 있다.
주요 연산
- 삽입(Insertion): 새로운 요소를 우선순위 큐에 추가
- 삭제(Deletion): 우선순위가 가장 높은 요소를 큐에서 제거
- 우선순위 확인(Peek): 우선순위가 가장 높은 요소를 제거하지 않고 반환
우선순위 큐 힙(Heap)
힙은 완전 이진 트리 형태의 자료 구조로, 각 노드가 자식 노드와 특정 순서 관계를 가진다. 주로 최소 힙(Min-Heap)과 최대 힙(Max-Heap)으로 구분된다.
- 최소 힙(Min-Heap):
- 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리다.
- 루트 노드(root node)에 가장 작은 값이 위치한다.
- 최대 힙(Max-Heap):
- 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리다.
- 루트 노드에 가장 큰 값이 위치한다.
힙의 주요 연산
- 삽입(Insertion): 새로운 요소를 힙에 추가하고 힙 속성을 유지합니다.
- 삭제(Deletion): 루트 노드(최솟값 또는 최댓값)를 제거하고 힙 속성을 유지합니다.
- 힙 정렬(Heap Sort): 힙을 사용하여 정렬을 수행합니다.
우선순위 큐 구현
- 배열을 사용한 구현:
- 비정렬 배열: 요소를 추가할 때는 O(1)의 시간 복잡도를 가지지만, 가장 높은 우선순위를 찾기 위해서는 O(n)의 시간이 필요하다.
- 정렬된 배열: 요소를 추가할 때는 O(n)의 시간 복잡도를 가지지만, 가장 높은 우선순위를 찾고 제거하는 작업은 O(1)의 시간이 필요하다.
- 힙(Heap)을 사용한 구현:
- 최소 힙(Min-Heap) 또는 최대 힙(Max-Heap): 요소를 추가하거나 제거할 때 O(log n)의 시간 복잡도를 가진다.
힙을 사용하면 우선순위 큐의 삽입과 삭제 연산이 매우 효율적으로 수행된다. 이는 힙의 삽입과 삭제가 O(log n)의 시간 복잡도를 가지기 때문이다.