우선순위 큐와 힙 이해하기

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)