큐(queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다.
우선순위 큐(priority queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. (우선순위: 최대 혹은 최소값이 먼저 나오는 구조)
즉, 우선순위의 개념을 큐에 도입한 자료구조로, 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다.
| 자료 구조 | 삭제되는 요소 |
|---|---|
| 스택(stack) | 가장 최근에 들어온 데이터 |
| 큐(queue) | 가장 먼저 들어온 데이터 |
| 우선순위 큐(priority queue) | 가장 우선순위가 높은 데이터 |
우선순위 큐는 배열, 연결리스트, 힙 으로 구현이 가능하다. 이 중에서 힙(heap)으로 구현하는 것이 가장 효율적이다.
| 우선순위 큐를
| 구현하는 표현 방법 | 삽입 | 삭제 |
|---|---|---|
| 순서 없는 배열 | O(1) | O(n) |
| 순서 없는 연결 리스트 | O(1) | O(n) |
| 정렬된 배열 | O(n) | O(1) |
| 정렬된 연결 리스트 | O(n) | O(1) |
| 힙(heap) | O(logn) | O(logn) |
완전이진트리 형태의 자료구조이다.최댓값 또는 최솟값을 찾아내는 연산이 빠르다.*힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)*부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리이다.