Chapter 09. 우선순위 큐의 이해

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

앞서 배웠던 '큐'의 핵심 연산 두 가지는 다음과 같았습니다.

• enqueue    큐에 데이터를 삽입하는 행위
• dequeue    큐에서 데이터를 꺼내는 행위

 

이와 마찬가지로 '우선순위 큐'의 핵심 연산 두 가지도 다음과 같습니다.

• enqueue    우선순위 큐에 데이터를 삽입하는 행위
• dequeue    우선순위 큐에서 데이터를 꺼내는 행위

 

반면 연산의 결과에는 차이가 있습니다. 큐는 연산의 결과로, 먼저 들어간 데이터가 먼저 나오지만, 우선순위 큐의 연산 결과는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나옵니다. 때문에 큐를 가리켜 '줄 서기'에 비유한다면, 우선순위 큐는 '응급상황'에 비유할 수 있습니다. 응급실에 들어오는 환자는 응급실에 들어온 순서가 아닌 우선순위에 따라서 치료를 받기 때문입니다.

 

우선순위에서 중요한 것은 우선순위입니다. 하지만 그렇다고 해서 각 데이터마다 우선순위를 저장하고 있어야 하는 것은 아닙니다. 데이터가 우선순위 정보를 가지고 있는 것이 아닌, 데이터를 근거로 우선순위를 판단할 수 있어야 합니다. 데이터의 우선순위를 어떻게 판단할 것인지는 프로그래머가 결정하기 나름입니다.

---

우선순위 큐를 구현하는 방법은 다음과 같이 세 가지로 구분할 수 있습니다.

• 배열을 기반으로 구현하는 방법
• 연결 리스트를 기반으로 구현하는 방법
• 힙(heap)을 이용하는 방법

 

배열이나 연결 리스트를 이용하면 우선순위 큐를 매우 간단히 구현할 수 있습니다. 데이터가 입력되면 해당 데이터의 우선순위를 판단하고, 배열이나 연결 리스트에 저장되어 있는 데이터들의 우선순위와 비교합니다. 그리고 그 우선순위에 따라서 출력 위치와 가까이 혹은 멀리 배치하면 됩니다.

 

하지만 이런 방식은 데이터의 수가 많아질수록 연산의 횟수가 늘어나는 좋지 못한 시간 복잡도를 보입니다. 왜냐하면 데이터를 새로 입력받을 때마다 기존에 저장된 모든 데이터와 우선순위를 비교해야 하고, 배열의 경우에는 데이터를 배열의 중간에 저장할 때 데이터들을 옆으로 복사해서 옮겨야 하기 때문입니다. 그래서 우선순위 큐는 단순 배열도, 연결 리스트도 아닌 '힙'이라는 자료구조를 이용해서 구현하는 것이 일반적입니다.

---

우선순위 큐를 힙을 이용해서 구현한다고 했는데 힙이란 무엇인지 모릅니다. 따라서 우선은 힙에 대해서 먼저 설명합니다. 힙은 다음과 같은 특징을 가집니다.

• 완전 이진 트리이다.
• 한 노드의 값은 그의 자식 노드들의 값보다 크거나 같아야 한다.

 

위에서 말하는 값은 정말로 값을 의미하기도 하고, 우선순위를 의미하기도 합니다. 힙을 그림으로 표현하면 다음과 같습니다.

위 그림처럼 부모 노드로 갈수록 값이 커져서 루트 노드의 값이 가장 큰 형태의 힙을 '최대 힙'이라고 합니다. 반면, 아래와 같이 부모 노드로 갈수록 값이 작아져 루트 노드의 값이 가장 작은 형태의 힙을 '최소 힙'이라고 합니다.