[Section 5] 우선 순위 큐의 개념과 종류 &시간 복잡도

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

우선순위 큐는 일반적인 큐와 다르게 최솟값과 최댓값 원소를 찾아내는데 더 적합한 방식의 자료구조이다. 이것은 최댓값과 최솟값을 중심으로 삽입과 삭제를 구현화했기 때문인데, 우선순위 큐의 개념과 종류에 대해 자세히 알아보도록 하자.

1. 개념 이해 _ 우선순위 큐(Priority Queues)

큐는 FILO 혹은 LILO 방식으로 데이터를 일렬로 처리하기 때문에 데이터의 삽입 또는 삭제에 해당하는 시간 복잡도는 O(1)이었다. 만약 큐와 같은 방식으로 최댓값 혹은 최솟값 데이터를 차례대로 정렬하면 어떻게 될까? 우리는 자료의 최댓값, 최솟값을 알기 위해 따로 탐색을 할 필요가 없다. 이것이 우선순위 큐의 가장 기본적인 개념이며, 우선순위 큐에 탐색 알고리즘이 필요 없는 이유이다. 

 

기본 원리는 큐와 동일하기 때문에 데이터의 삽입과 삭제 용어도 각각 인큐(EnQueue)와 디큐(Dequeue)로 동일하다. 때때로 우선순위 큐는 오름차순 큐(ascending-priority queue) 혹은 내림차순 큐(descending-priority queue)라는 용어로 불리기도 하니 참고하도록 하자.

 

우선순위 큐의 주 ADT에 대해 알아보자. 먼저, 데이터의 삽입 과정에서 키(key)라 불리는 데이터가 같이 삽입된다. 이 키를 통해서 데이터의 최댓값과 최솟값을 반환하는 기능을 추가할 수 있다. 다음으로 보조 ADT는 k번째로 가장 크거나 작은 원소를 찾는 기능이 존재한다. 그리고 사용자의 편의에 따라 자료 구조의 전체 사이즈를 반환하는 기능 등이 존재하겠다.

2.  우선 순위 큐의 종류와 시간 복잡도 비교 _ 배열, 리스트, 트리, 그리고 힙

우선순위 큐는 선형 혹은 비-선형 자료구조 형태로 구현이 모두 가능하다. 그리고 그 종류는 정렬되거나 정렬되지 않은 데이터 구조로 분류되는데, 가장 기본적으로 배열 혹은 리스트 형태로 우선순위 큐를 구현할 수 있다.

 

* 우선순위 큐의 정렬 기준은 데이터의 키 속성에 달려있다.

 

추가로 트리(Binary Search Trees, Balanced Binary Search Trees)와 힙(Binary Heap)으로도 우선 순위 큐를 구현할 수 있다. 종류에 따른 시간 복잡도 특성은 다음의 표로 요약된다.

 

우선 순위 큐의 종류	삽입	삭제(최댓값 순서)	최솟값 검색
정렬/ 정렬되지 않은 배열	n / 1	1 / n	1 / n
정렬/ 정렬되지 않은 리스트	n / 1	1 / n	1 / n
BST(Binary Search Trees)	log n	log n	log n
Balanced BST	log n	log n	log n
Binary Heaps	log n	log n	1