[Swift] Heap을 이용한 Priority Queue 구현

우선순위 큐(Priority Queue)는 이름에서 알 수 있듯이 큐(Queue)의 일종이다. 큐는 지난 포스팅에서 설명한 것과 같이, 먼저 입력된 데이터가 먼저 출력되는 자료구조이다. 이에 반해 우선순위 큐는 출력될 데이터가 입력된 순서에 따라 결정되는 것이 아니라, 우선순위에 따라 이루어진다는 차이가 있다. 

 

우선순위 큐도 다양한 방법으로 구현할 수 있지만, 힙으로 구현하는 것이 적절해 보인다. 배열(Array)이나 연결 리스트(Linked List)로 구현할 경우, 삽입 또는 삭제 연산 시에 데이터의 정렬을 위해 모든 데이터를 순회해야 하기 때문에 시간 복잡도가 O(n)이 소요된다. 하지만 힙의 경우 삽입 또는 삭제 시에 반정렬 상태만 유지하면 되는 완전 이진 트리이기 때문에 시간 복잡도가 O(lb(n))이 소요된다. 이러한 이유로 배열이나 연결 리스트로 구현하는 것보다 힙으로 구현하는 것이 시간 복잡도 측면에서 유리하다. 

(lb(n)은 밑을 2로 갖는 로그 n)

 

큐나 리스트(List)가 연결 리스트를 상속하여 구현한 것과 비슷하게 우선순위 큐는 힙을 상속하여 구현할 것이다. 힙 클래스에 대한 구현은 지난 포스팅(https://taeminator1.tistory.com/43)을 참고하면 된다. 

 

아래 클래스 다이어그램을 살펴보자. 

큐에서와 마찬가지로 pop() 연산을 정의하였다. 해당 연산은 힙 클래스에서 구현한 remove 연산을 이용하여 쉽게 구현할 수 있다. 사실 remove 연산 시에 index가 0인 경우가 pop 연산이다. 

 

그래서 다음과 같은 코드만 추가하면 우선순위 큐를 쉽게 구현할 수 있다. 

 

힙 클래스와 마찬가지로 우선순위 큐의 인스턴스를 생성할 때, 부모 노드와 자식 노드 간의 조건을 정해주면 된다. 다시 말해 어떤 노드를 더 높은 우선순위로 지정할지 정해주면 된다. 아래의 예에서는 노드의 값이 작을수록 우선순위가 높게(최소 힙으로) 설정을 해주었고, 데이터의 타입은 String으로 설정해주었다. 

insert 메서드는 Heap 클래스에서 확인한 것과 같이 잘 실행이 되었고, pop 메서드도 우선순위가 높은 것부터 차례로 잘 반환되고 반정렬 상태를 잘 유지하는 것을 확인했다.