우선순위 큐 Priority Queue

큐(Queue)는 우선순위와 상관없이 먼저 들어간 데이터가 먼저 나오는 FIFO 방식의 자료구조이다. 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 우선적으로 나오는 자료구조이다. 그렇다면 우선순위 큐는 어떻게 구현할 수 있을까?

---

 

 

1. 배열로 우선순위 큐 구현하기

Array

 우선순위대로 데이터들이 들어온다고 가정했을 때,  우선순위대로 앞의 인덱스부터 채워나가면 되기 때문에 문제가 되지 않는다.(데이터가 모두 들어오고 난 뒤에는 정렬된 상태) 하지만 연속적인 우선 순위 데이터의 입력이 보장되지 않을 경우에는 우선 순위에 맞춰 데이터를 이동시켜야 한다.

이렇게 할 경우 처음 인덱스부터 우선순위를 비교해야 하기 때문에 데이터 삽입의 최악의 시간 복잡도는 O(n)이 걸리게 된다.

 

Enqueue : O(n)

Dequeue : O(1)

 

2. 연결리스트로 우선순위 큐 구현하기

Linked List

연결리스트도 배열과 마찬가지로 데이터의 삽입에 있어서 최대 O(n), 우선순위가 높은 데이터의 삭제는 O(1)의 시간 복잡도를 가진다. 다만 우선순위가 높은 데이터를 삭제 후 데이터의 이동이 필요하지 않기 때문에 배열보다 빠르다.

 

Enqueue : O(n)

Dequeue : O(1)

 

3. 힙

힙은 완전 이진트리 구조로 우선순위 큐를 표현하기에 최적인 자료구조의 형태이다. 완전 이진트리는 부모노드의 우선순위가 자식 노드의 우선순위보다 같거나 높다. 여기서 같은 경우는 데이터의 중복이 가능하다는 의미이다. 따라서 루트 노드에는 항상 우선순위가 가장 높은 데이터가 들어있고, 아래로 갈수록 우선순위가 낮아진다. 

 

데이터의 삽입과정

1. 삽입 하려는 데이터는 제일 마지막 노드에 삽입한다.
2. 마지막 노드에 삽입된 데이터는 부모노드와 비교하여 우선 순위가 높은 경우 부모노드와 자리를 바꾼다.

데이터를 삽입할 때 데이터는 마지막 노드로 들어가게 된다. 그리고 부모 노드와 비교를 통해 자리를 결정한다. 형제 노드와는 비교를 하지 않는다. 즉 레벨 당 한번의 비교만 이루어지게 되어 전체 노드가 n이라면  최대 O(logn)의 시간복잡도를 소요하게 된다.

인덱스마다 한번씩 비교를 해 O(n)의 시간이 걸리는 배열보다도 훨씬 빠른 속도이다.

 

데이터의 삭제과정

1. 루트 노드의 데이터를 삭제한다.
2. 마지막 노드의 데이터를 루트노드에 가져온다.
3. 루트노드의 데이터와 자식노드의 데이터를 비교한다.
4. 자식 노드의 데이터가 더 크다면 루트노드와 위치를 바꾼다.
5. 다시 자식노드들과 우선순위를 비교하여 자식노드보다 작다면 자식노드와 위치를 바꾼다.

삭제의 경우 배열보다 느리다. 하지만 배열도 마찬가지로 데이터를 삭제했다면 반드시 데이터 이동을 반드시 필요로 하게 된다. 이 점에서 봤을 때 힙으로 구현한 우선순위 큐가 O(logn)의 시간이 걸리므로 배열보다 더 빠르다.

힙의 종류

1. 최대힙(Max Heap)

루트로 갈수록 우선순위가 높아짐

 

2. 최소힙(Min Heap)

루트로 갈수록 우선순위가 낮아짐

 

4. 힙을 배열로 구현한다면?

배열로 힙을 구현하기 위해 트리의 노드 번호 규칙을 잘 알고 있어야 한다.

1번 노드는 2, 3의 자식 노드를 가지고 있고,

2번의 경우 4, 5

3번의 경우 6, 7

...

n번의 경우 2n, 2n + 1의 자식 노드를 가지고 있다.

이 점을 이용해서 우선순위 큐를 만들 수 있다.

 

데이터 삽입의 경우

-> 마지막 노드에 데이터를 넣고 부모 노드와 비교하며 자신의 위치를 찾는다.

//삽입하려는 데이터의 노드가 루트노드를 가리키고 데이터의 값이 부모 노드보다 작으면 반복문 빠져나옴
while(i != 1 && data > heap[i/2]) {
	heap[i] = heap[i/2];
    i = i/2;
}
 heap[i] = data;

 

데이터 삭제의 경우

-> 루트 노드를 삭제시키고 마지막 노드를 루트노드로 올려서 자식 노드들과 비교