[자료구조] Priority Queue (우선순위 큐) 인터뷰 대비

 

💡 1. 우선순위 큐(Priority Queue)란?

 

우선 '큐'는 선입선출의 구조를 가진 선형 자료구조이다. 큐에 들어온 순서를 우선순위로 갖는 큐인 것이다.

우선순위 큐는 일반적으로 먼저 들어온 순서대로 빠져나오는 것이 아니라, 큐 내부의 원소 중 가장 우선순위가 가장 높은 요소부터 빠져 나오는 큐를 의미한다.

 

 

💡 2. 우선순위 큐를 구현하는 방법

 

 우선순위 큐를 구현하는 방법은 세 가지이다.

각각 배열(Array), 연결리스트(LinkedList), 힙(Heap)을 사용하는 방법인데 그 중 일반적으로 우선순위 큐를 구현하는 방법은 Heap을 사용하는 방식이다. 왜 우선순위 큐를 구현할 때 Heap을 사용하는 지는 바로 시간복잡도에 있다.

 

다음은 각각의 자료구조를 사용해 우선순위 큐를 구현하는 방법이다.

 

1) 배열(Array)를 이용해서 우선순위 큐를 만들기.

배열로 우선순위 큐를 만드는 방법은, 정렬된 배열을 이용하는 방법 / 정렬되지 않은 배열을 이용하는 방법 2가지이다.
큐는 기본적으로 삽입과 삭제 연산이 있으므로, 이 두 가지 연산을 어떻게 만들 수 있을지 생각해보자.

- 정렬된 배열로 우선순위 큐 만들기 (우선순위를 key값으로 정렬된 배열)
삭제의 경우, 우선순위 순서대로 정렬이 되어 있으므로, 가장 앞의 원소를 return 하면 된다. 따라서 삭제의 시간복잡도는 O(1)
삽입의 경우, 삽입할 요소의 우선순위가 어느 위치에 들어가야 하는지 요소 하나하나 비교해서 찾아야 하므로, 최악의 경우 배열의 길이인 N만큼의 연산이 필요하다. 따라서 삽입의 시간복잡도는 O(N)

- 정렬되지 않은 배열로 우선순위 큐 만들기
삭제의 경우, 배열 내부는 정렬되어 있지 않기 때문에 배열 내부의 모든 원소를 비교해 가장 높은 우선순위의 값을 찾아 제거해야 한다. 무조건 N번의 연산을 거쳐야 하므로 삭제의 시간복잡도는 O(N)에 해당한다.
삽입의 경우, 배열 내부는 정렬되어 있지 않기 때문에, 별다른 규칙 없이 배열의 끝 부분에 요소를 삽입하면 된다. 따라서 삽입의 시간 복잡도는 O(1)이다.

 

2) 연결리스트(LinkedList)를 이용해서 우선순위 큐를 만들기.

연결리스트로 우선순위 큐를 만드는 방법 역시, 정렬된 연결리스트를 이용하는 방법 / 정렬되지 않은 연결리스트를 이용하는 방법 2가지이다.
마찬가지로 삽입과 삭제 연산을 어떻게 만들 수 있을지 생각해보자.

- 정렬된 연결리스트로 우선순위 큐 만들기
삭제의 경우, 배열과 동일하게 가장 앞의 원소를 제거하면 된다. O(1)
삽입의 경우, 배열과 동일하게 삽입하고자 하는 원소가 어느 자리에 들어가야 하는지 연결리스트 내부의 원소를 지나가며 탐색해야 한다. 최악의 경우 N개의 요소를 모두 탐색해야 하기 때문에 worst case의 경우 O(N)
배열과 슷한 시간복잡도를 가지나, 연결리스트의 특성상 배열보다 삭제와 삽입의 연산이 단순하기 때문에 배열보다는 유리하다.

- 정렬되지 않은 연결리스트로 우선순위 큐 만들기
삭제의 경우, 배열과 동일하게 삭제하고자 하는 원소를 연결리스트 내부를 모두 탐색하며 찾아내야 한다. 따라서 시간복잡도는 O(N)이다.
삽입의 경우, 연결리스트 내부에 아무런 규칙이 없으므로 가장 넣기 쉬운 위치인 앞에 삽입한다. 따라서 시간복잡도는 O(1)이다.
배열과 비슷한 시간복잡도를 가지나, 연결리스트의 특성상 배열보다 삭제와 삽입의 연산이 단순하기 때문에 배열보다는 유리하다.

 

3) 힙(Heap)을 이용해서 우선순위 큐를 만들기

힙이 되기 위한 조건은 2가지이다. 완전이진트리의 구조를 가지며, 부모노드와 자식 노드간에 '크거나 같은' 혹은 '작거나 같은'의 규칙을 가지고 있어야 한다. 이 힙을 이용해서 우선순위 큐를 만드는 방법에 대해 살펴보자.
역시 삽입과 삭제의 관점에서 확인해보도록 하자.

- Heap으로 우선순위 큐 만들기
우선, 위의 힙이 되기 위한 조건에 부모노드와 자식 노드간에 '크거나 같은' 혹은 '작거나 같은'의 규칙을 가지고 있어야 된다.
따라서 우선순위가 가장 큰 값이 오도록 힙이 구성되어 있다면, 루트노드에 있는 값을 리턴하고, 트리에서 해당 노드를 삭제하고, 다시 힙으로 만들면 삭제 연산이 된다.

삭제 연산 알고리즘은 다음과 같다.
1) 루트노드의 값을 리턴한다. (O(1))
2) 가장 마지막 인덱스를 가진 노드를 루트노드 자리에 위치시킨다. (O(1))
3) 루트노드와 두 자식 노드를 비교한다. 두 자식노드 중 부모노드보다 우선순위가 큰 노드가 있다면 가장 우선순위가 큰 노드와 자리를 변경한다. 자리를 변경한 후, 변경한 후의 자식과도 계속 비교한다. 자식보다 우선순위가 크다면 이 반복을 중단한다. (O(logN))

여기서 3번의 경우, 트리의 높이 만큼 연산이 진행되고 힙은 '완전이진트리'라고 했으므로 worst case인 경우 밑이 2인 logN번의 연산을 수행한다. 따라서 1~3번의 순서대로 연산을 진행했을 때 삭제 연산의 worst case는 O(logN)의 시간 복잡도를 가진다.

삽입 연산 알고리즘은 다음과 같다.
1) 가장 마지막 인덱스 다음 인덱스에 삽입하고자 하는 노드를 넣는다. (O(1))
2) 해당 값과 부모노드의 우선순위를 비교한다. 해당 값(자식노드)이 부모노드보다 우선순위가 더 높다면 서로 자리를 변경한다. 자리를 바꾼 이후에도 그 위의 부모노드와 비교하며, 부모노드의 우선순위가 더 클 때까지 반복한다. (O(logN))

삽입 연산도 마찬가지로, worst case인 경우 제일 밑에서 루트노드까지 올라올 수 있으므로 트리의 높이만큼 연산이 된다. 따라서 삽입 연산도 O(logN)의 시간복잡도를 가진다.

 

 

4) 시간복잡도 비교 및 Heap 선택 이유

우선순위 큐 구현에 사용한 자료구조	worst case 삽입연산	worst case 삭제
정렬된 배열	O(N)	O(1)
정렬되지 않은 배열	O(1)	O(N)
정렬된 연결리스트	O(N)	O(1)
정렬되지 않은 연결리스트	O(1)	O(N)
Heap 자료구조	O(logN)	O(logN)

 

다른 알고리즘은 삽입과 삭제 연산이 O(1), O(N)으로 두 연산간 시간복잡도 편차가 크다.

반면 힙으로 구현한 우선순위 큐는, 삽입과 삭제 연산 모두 트리의 높이에 따라 결정되는 O(logN)의 시간복잡도를 갖는다.

 

시간복잡도 편차가 크면 원소의 양과 연산의 양이 늘어날 수록 연산 시간이 오래걸린다.

배열/연결리스트의 경우 동일한 횟수의 삽입과 삭제를 하면 kN + k번, 힙을 사용한 경우엔 2*klogN번 연산이 진행된다.

N의 기울기는 logN의 기울기보다 훨씬 가파르기 때문에 원소의 양이 늘어난다면 시간이 훨씬 더 많이 소요되게 된다.

따라서 삽입과 삭제 모두 O(logN)의 시간복잡도가 보장된 힙을 사용하는 것이 우선순위 큐를 구현할 때 더 유리하다.

 

+ Heap에 대한 자세한 내용은 추후 포스팅하도록 하겠습니다.