우선순위 큐와 힙 이해하기
1. 우선순위 큐 정의
큐는 먼저 들어온 데이터가 먼저 출력됩니다. 반면, 우선순위 큐는 모든 데이터가 우선순위를 가지고 있고, 이로 인해 들어온 순서에 관계 없이 우선순위가 높은 순으로 데이터가 나가는 형태의 자료구조입니다.
우선순위 큐의 특징
- 모든 요소들은 우선순위를 가지고 있어, 요소를 삽입할 때, 우선순위에 따라 정렬됩니다
- 가장 높은 우선순위 요소가 먼저 삭제됩니다
- 힙으로 구현된 자료구조입니다
위 사진과 같은 상황에서 12가 들어온다고 가정해봅시다
- 삽입(enqueue) 시, 가장 높은 우선순위인 12가 배열의 가장 앞쪽에 위치
- 삭제(dequeue) 시, 가장 높은 우선순위인 12가 배열의 앞쪽에 위치해있기 때문에 삭제합니다
- 삭제 후, 자식 요소 중 다음으로 높은 우선순위를 가진 요소가 앞에 위치합니다
우선순위 큐는 삽입 / 삭제 시간복잡도가 모두 O(log n)인데, 힙 구조로 이루어져있기 때문에 힙을 자세히 알아보면서, 그 이유에 대해 설명하겠습니다
2. 힙의 정의
*힙이란?
힙은 여러 개들의 값들 중에서 가장 큰 값이나, 가장 작은 값을 찾아내도록 고안된 자료구조
2-1. 힙의 특징
- 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(or 작은) 이진 트리를 지칭
- 이진 탐색 트리와 달리 힙에서는 중복된 값을 허용
- 완전 이진 트리 형태로 구성
*아래 링크는 이진 트리에 대한 설명
https://rosweet-ai.tistory.com/55
2-2. 힙의 구현
힙(Heap)은 큰 값(or 작은 값)을 효율적으로 찾아내기 위한 자료구조로, 내부 요소들이 완전히 정렬될 필요는 없습니다.
힙은 부모 노드와 자식 노드 간의 관계만 유지하면 되는데,
- 모든 부모가 자식보다 작거나 같으면 → 최소 힙(Min Heap)
- 모든 부모가 자식보다 크거나 같으면 → 최대 힙(Max Heap) 이라고 부릅니다.
힙은 완전 이진 트리 구조이며, 높이는 log₂(n+1)에 가까우므로, 삽입이나 삭제 시의 시간 복잡도는 O(log n)입니다.
삽입 시, 내부적으로 정렬되면 삭제 시, 시간 복잡도는 O(1)으로 보일 수 있지만, 내부적인 삭제 연산 과정이 존재하기 때문에
삽입 / 삭제 모두 시간 복잡도는 O(log n)입니다. 힙 구조를 설명하면서 그 이유에 대해 알아보겠습니다
힙은 완전이진트리이기 때문에, 중간에 비어 있는 요소 없이 차례대로 번호를 붙일 수 있습니다.
이는, 배열의 인덱스를 손쉽게 계산할 수 있음을 시사합니다
- 배열의 왼쪽 인덱스 = 부모 인덱스 * 2 (ex. 부모 index가 1이면, 왼쪽 인덱스는 2)
- 배열의 오른쪽 인덱스 = 부모 인덱스 * 2 + 1 (ex. 부모 index가 1이면, 오른쪽 인덱스는 3)
위와 같이, 간단한 인덱스 계산 식을 통해서 배열의 인덱스를 계산할 수 있습니다
반대로, 부모의 인덱스를 알고 싶다면 자식 인덱스 / 2를 해주면 되겠죠?
2-2. 힙의 삽입 및 삭제 과정
I. 힙의 삽입
- 새로운 노드가 삽입 될 때, '우선순위에 관계 없이' 가장 마지막에 위치합니다
- 이후, 부모 노드와 교환을 반복합니다(heapify)
*heapify란?
힙 속성을 만족하도록, 배열을 정렬하는 과정
II. 힙의 삭제 (최소 힙 기준)
- 부모 노드인 1이 삭제됩니다.
- 그 자리에는 배열의 가장 마지막 요소가 위치합니다
- 이후, 적절한 위치에 배치되기 위하여, 부모 노드와 교환을 반복합니다 (heapify)
이를 통해서, 힙(heap)의 시간복잡도가 O(log n)임을 알 수 있습니다
새 노드 삽입 시, 노드들이 정렬(heapify)되더라도, 삭제 시 동일한 정렬 과정(heapify)이 일어나야하기 때문에
삽입과 삭제 모두 O(log n)이 소요되는 것입니다.
3. 우선순위 큐 시간복잡도
| 구현 방법(큐) | enqueue() | dequeue() |
| 배열 | O(1) | O(N) |
| 연결 리스트 | O(1) | O(N) |
| 힙 | O(logN) | O(logN) |