우선순위 큐 (Priority Queue) 란?

우선순위 큐란?

각 요소가 우선순위를 갖고 있는 자료구조를 말합니다.

일반적인 큐와는 다르게, 입력된 순서와 상관없이 우선순위가 가장 높은 데이터를 가장 먼저 출력하게 됩니다.

 

우선순위 큐는 Heap을 이용하여, 구현된 자료구조입니다.

우선순위는 배열과 연결리스트로도 구현할 수도 있지만, 최악의 경우에 우선순위 찾기 위해 인덱스의 끝까지 탐색할 수 있기 때문입니다. 

Heap을 사용한다면, 새 데이터 삽입 시, O(log2N)  그리고 데이터 삭제 시, O(log2N) 입니다.

👇  배열, 연결리스트, 힙 시간 복잡도 비교

---

배열

: 우선순위가 높은 순서대로 배열의 가장 앞 부분부터 넣는다면, 우선순위가 높은 데이터를 반환하는 것(삭제)은 맨 앞의 인덱스를 바로 이용하면 되므로 어렵지는 않습니다. 시간 복잡도는 O(1)입니다.

하지만, 우선순위가 중간인 것이 들어가야 하는 데이터 넣는 과정(삽입)에서 데이터까지 인덱스를 모두 한 칸 씩 뒤로 밀어야하는 단점이 있습니다. 최악의 경우 삽입해야 하는 위치를 찾기 위해 모든 인덱스를 탐색해야해서, 이 때의 시간 복잡도는 O(n)이 됩니다.

 

연결리스트

: 우선순위가 높은 순서대로 연결 시킨다면, 배열과 동일하게, 데이터 반환(삭제)는 쉽습니다.  시간 복잡도는 O(1)입니다.

하지만, 삽입 과정은 배열과 마찬가지로 그 위치를 찾기 위해서 최악의 경우 맨 끝까지 가 삽입 시, 시간복잡도가 O(n) 이 됩니다.

 

힙

: 힙은 삭제와 삽입 과정에서 모두 부모와 자식간의 비교만 계속 이루어지게 됩니다.

즉 , 이진 트리의 높이가 하나 증가할 때마다 저장 가능한 자료의 갯수는 2배 증가하며, 비교 연산 횟수는 1회 증가하게 됩니다.

삭제와 삽입은 시간복잡도가 O(log2N) 입니다.

---

그래서 일반적으로 Heap을 구현체로 사용하게 됩니다.

 

데이터를 삽입할 때, 우선순위를 기준으로 최대힙 또는 최소힙을 구성하고, 데이터를 꺼낼 때, 루트 노드를 꺼냅니다.

루트 노드를 삭제할 때는 ?

빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후, 아래로 내려가면서 적절한 자리를 찾아서 옮깁니다.

 

그리고 Priority Queue 는 ADT(추상 자료형(Abstract Data Type)) 라고합니다. 그리고 Heap 자료구조를 구현체로 사용합니다.

아래에서 힙에 대해서 잠깐 간략하게 정리를 해보겠습니다.

---

 

Heap (힙)

힙은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조입니다.

여러 개의 값 중 최대값 또는 최솟값을 찾아내는 연산이  빠릅니다.

 

Heap 의 특징

• 완전이진트리 형태로 이루어져 있습니다.
• 부모노드와 서브트리 간 대소 관계가 성립됩니다. (반 정렬 상태)
• 이진탐색트리(BST)와 달리 중복된 값이 허용됩니다.

👇 완전이진트리 란?

---

루트(root) 노드부터 시작하여, 왼쪽 자식노드, 오른쪽 자식노드 순서대로 데이터가 차례대로 삽입되는 트리를 의미합니다.

---

Heap 의 종류

• 최대 힙 (Max Heap) : 부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리입니다.
• 최소 힙 (Min Heap) : 부모 노드의 키 값이 자식 노드보다 작거나 같은 완전이진트리 입니다.

Heap 구조에서는 삽입, 삭제 연산이 일반 트리구조의 삽입, 삭제 연산과는 조금 다릅니다.

삽입 연산은 아래에서  위로 벼교 작업을 수행하고, 삭제연산은 루트노드를 삭제하고, 마지막노드를 루트노드의 자리를 올려 위에서부터 아래로 비교 연산을 수행합니다.

따라서, Heap 구조에서는 각 키 값의 인덱스를 확실히 알고 있는 것이 일의 효율을 높일 수 있기 때문에 순차 자료구조 즉, 배열을 이용하여 구한하는 것이 좋습니다.

 

[이진탐색 트리 삽입연산]

Heap 에서 삽입 연산은 완전 이진트리의 형태를 유지하기 위해서 현재의 마지막 노드의 다음자리를 확장하여, 만든 자리에 삽입할 노드를 임시로 저장합니다. 이 후, 키 값의 관계가 최대 힙이 될수 있도록 재구성하기 위해 삽입한 노드의 키 값과 부모 노드의 키 값을 비교하면서 아래에서 위로 자리를 찾아가는 비교작업을 수행합니다.

 

 

[이진탐색 트리 삭제연산]

Heap 에서 삭제 연산은 항상 루트 노드에 있는 원소를 삭제하여 반환합니다.

그러므로, 최대 힙에서의 삭제연산은 키 값이 가장 큰 원소를 삭제하여 반환하고, 최소 힙에서는 키 값이 가장 작은 원소를 삭제하여 반환하게 됩니다.

삭제연산 역시 삽입연산과 동일하게, 완전 이진트리의 형태를 유지하기 위해서 완전 이진트리의 가장 마지막 노드를 삭제한 후, 루트 노드의 자리에 임시로 삽입하여 자식 노드와 비교작업을 수행하면서 제 위치를 찾을 수 있도록 합니다.

 

 

 

우선순위 큐와 큐의 차이점은?

일반적인 큐는 선형 구조를 가지고 있지만,

우선순위 큐는 트리(Tree) 구조로 보는 것이 합리적입니다.

 

우선순위 큐와 힙의 차이점은?

단순히 insert/remove methods만 사용한다면, 차이점은 없다. 데이터 자체의 값인 queue/data 를 통과해야 하는 경우 우선순위 큐를 통해 이러한 값의 정렬된 목록에 접근할 수 있으며 힙은 그렇지 않다.