8-2. 우선순위 큐의 구현 방법
우선순위 큐의 구현 방법
우선순위 큐를 구현하는 방법은 여러가지가 있다. (배열, 연결 리스트, 힙 등)
배열을 이용하는 방법
정렬되지 않은 배열을 이용하는 방법
정렬되지 않은 배열을 사용하면 삽입 연산은 간단하다. 그냥 기존 요소들 맨 끝에 새로운 데이터를 붙이면 된다.
따라서 시간 복잡도는 O(1)이 된다.
그러나 삭제 연산의 경우는 요소들을 처음부터 끝까지 검사하면서 우선순위가 가장 높은 요소를 찾아야 한다.
배열이 정렬되어 있지 않기 때문이고, 이때 시간 복잡도는 O(n)이 된다.
삭제를 한다고 끝이 아니다. 삭제한 요소 뒤에 있는 요소들을 앞으로 한 칸씩 이동시키는 작업도 필요하다.
정렬된 배열을 이용하는 방법
정렬이 되어 있는 배열에 새로운 요소를 삽입하는 경우 기존 요소들과 우선순위를 비교하는 과정이 필요하다.
비교를 통해 삽입 위치를 찾고 그 위치에 삽입해야 배열을 계속 정렬된 상태로 유지할 수 있기 때문이다.
적당한 삽입 위치를 찾으면 기존 요소들을 뒤로 한 칸씩 이동시켜 삽입을 위한 자리를 만들어야 한다.
따라서 삽입 연산의 시간 복잡도는 O(n)이 된다.
삭제 연산의 경우는 간단하다.
배열이 정렬되어 있으므로 배열 맨 뒤에 있는 요소가 우선순위가 가장 높은 요소일 것이다.
그 요소를 삭제만 하면 되고, 시간 복잡도는 O(1)이 된다.
연결 리스트를 이용하는 방법
연결 리스트를 이용하는 방법도 배열을 이용하는 방법과 크게 다르지 않다.
정렬되지 않은 연결 리스트를 이용하는 방법
삽입 시 기존 노드 제일 앞 쪽에 새로운 데이터를 붙이기만 하면 된다.
배열과 달리 기존 노드들을 한 칸씩 이동시킬 필요는 없다. 시간 복잡도는 O(1)이 된다.
삭제 시에는 포인터를 따라서 기존 노드들을 검사해 우선순위가 가장 높은 노드를 찾아야 한다.
따라서 시간 복잡도는 O(n)이 된다.
정렬된 연결 리스트를 이용하는 방법
삽입 시 기존 노드들을 검사해 삽입 위치를 찾고 그 위치에 새로운 데이터를 삽입하면 된다.
시간 복잡도는 O(n)이 된다.
삭제 시에는 첫 번째 노드를 삭제하면 되므로 시간 복잡도는 O(1)이 된다.
힙을 사용하는 방법
힙(heap)은 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다.
힙은 반 정렬 상태를 유지한다. 즉, 요소들이 완전히 정렬된 것도 아니고 전혀 정렬되지 않은 것도 아닌 상태이다.
힙의 삽입/삭제 시간 복잡도는 모두 O(log2n)으로 위에 소개한 두 방법보다 좋다.
n이 1024라면 O(n)의 시간 복잡도를 갖는 알고리즘은 1024초가 걸리겠지만 O(log2n)의 시간 복잡도를 갖는 알고리즘의 경우 10초 밖에 걸리지 않으므로 n이 커질수록 이 차이는 극명하게 드러날 것이다.
