[자료구조] 우선순위 큐(Priority Queue) - 1

 

큐는 연산의 결과로 먼저 들어간 데이터가 먼저 나오나 우선순위 큐는 다르다.

 

들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

 

일상 예제로 병원의 응급실을 예로 들어보면

물론 모든 환자분들이 빠른 치료를 받고 완치가 되면 좋겟지만

제일 응급한 환자부터 치료를 하게 된다.

 

즉 우선순위가 높은 환자가 먼저 치료를 받는 것이다.

 

이렇게 우선순위 큐에서 중요한 것은 우선순위 이다.

데이터를 근거로 우선순위를 판단해야 되고 목적에 맞게 우선순위를 프로그래머가 판단해서 결정해야 되는 일이다.

 

우선순위가 다른 데이터 뿐만 아니라 같은 데이터가 존재할 수도 있다.

 

우선순위 큐를 구현하는 방법은 세 가지로 나뉘어진다.

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

 

배열이나 연결리스트를 이용해서 우선순위 큐를 구현할 경우

간단하게 구현이 가능하다.

 

하지만 배열의 경우에는 이러한 단점이 따른다.

"데이터 삽입 및 삭제과정에서 데이터를 한 칸씩 당기거나 밀어야 하는 연산을 계속 하여야 한다."

그리고 또 하나의 문제가 있다.

"삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야 한다."

이 경우는 우선순위가 가장 낮은 데이터를 저장하는 경우에 발생할 최악의 경우이다.

꼭 이런 최악의 경우가 아니더라도 이러한 일이 빈번하게 일어날수 있다.

 

그러면 연결리스트의 경우는 어떠할까??

배열의 첫번째 문제는 별로 되지 않지만

"삽입의 위치를 찾기 위해 첫번째 노드에서부터 시작해 마지막 노드에 저장된 데이터와 우선순위를 비교를 진행할지도 모른다."

이 경우 데이터가 적을 경우에는 별 단점이 될 수는 없겠지만 데이터가 많아질 때 노드의 수에 비례해서 비교할 대상이 증가하므로

성능이 저하된다.

 

그래서 우선순위 큐는 주로 힙(Heap)을 이용해서 구현하는 것이 일반적이다..

 

힙을 기반으로 우선 순위 큐를 구현하고자 한다.

힙의 구현을 위해서 데이터의 저장과 삭제 방법을 알아보자

(데이터의 저장 과정을 '최소 힙'을 기준으로 설명하려고 한다)

 

위 힙 구조안에 있는 숫자를 데이터겸 우선순위라고 하고

숫자가 작을수록 우선순위가 높다고 가정하자.

 

위 상황에서 2를 저장한다고 가정시….

새로운 데이터는 우선순위가 제일 낮다는 가정하에서 마지막 위치에 저장한다.

그리고 부모 노드와 우선순위를 비교하여 위치가 바뀌어야 한다면 바꿔주고

제 자리를 찾을때까지 반복한다.

 

위에서 언급한 '마지막 위치'는 노드를 추가한 이후에도 완전 이진 트리가 유지되는 마지막 레벨의 가장 오른쪽 위치를 의미 한다.

 

2를 마지막 위치에 추가를 한 뒤에 부모 노드인 7과 비교를 한다.

 

2와 7의 위치를 서로 바꾼 후 부모 노드 3과 비교를 한다.

 

3과 2의 위치를 바꾼 뒤 1과의 비교를 한다.

1과 비교를 하였을 때 2는 1보다 우선순위가 낮으므로 2는 제자리를 찾았다

 

위의 구조가 결과가 되는것인데 힙의 조건을 만족하고 있다.

 

추가 과정은 마지막 위치에 데이터를 두고 부모 노드와 비교를 통해서 자신의 위치를 찾아가면 된다.

 

그러면 위의 구조에서 삭제는 어떻게 구현이 될까?

 

우선순위 큐의 삭제는 가장 높은 우선 순위의 데이터 삭제를 의미 한다.

힙에서 루트 노드를 삭제한다는 것은 그다지 어렵지 않다.

하지만 루트 노드를 삭제한 뒤에 빈 루트노드를 어떻게 채울까???

 

이것이 문제다..

루트 노드의 저 빈곳을 채울 방법이 필요하다.

 

이 문제에 대한 전통적인 해결책은 다음과 같다.

마지막 노드를 루트 노드의 자리로 옮긴 뒤 자식 노드와의 비교를 통해 제자리를 찾아가게 한다!

 

마지막 노드를 루트 노드로 옮겼다.

 

그리고 자식 노드와의 비교를 한다.

이 때 두 개의 자식 노드중 우선 순위가 높은 노드와 교환을 해야 한다.

자식 노드 2와 6중에서 우선순위가 높은 2와 교환 한다.

자식 노드인 3과 9중 3의 우선 순위가 높으므로 3과 자리를 바꾼다.

 

자식 노드 20과 비교를 했을 때 우선순위가 7이 더 높으므로 현재 제자리를 잘 찾았다.