c++ 자료구조 - priority queue

백준 자료구조 문제를 풀다가 1966 프린터 큐 문제에서 우선순위 큐를 사용해서 그에 대한 내용을 정리해본다.

정의

일반적인 선형 자료구조인 큐에 우선순위 개념이 추가된 것이다. 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

속성

• 모든 항목에는 우선순위가 있습니다.
• 우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 큐에서 제외됩니다.
• 두 요소의 우선 순위가 같으면 큐의 순서에 따라 제공됩니다.

구현 방식

구현 방식에는 배열, 연결 리스트, 힙이 있다.
구현 방법에 대해서는 해당 링크에 설명되어 있다.

이 구현 방법의 시간 복잡도에 대해 간단히 설명을 하겠다.
(1) 우선순위 큐를 배열로 구현할 경우
우선순위가 높은 순서대로 배열의 가장 앞부분부터 넣는다.
우선순위가 높은 데이터를 반환하는 것은 맨 앞의 인덱스를 바로 이용하는 것이므로 어렵지 않다.
우선순위가 중간인 것이 들어가야 하는 삽입 과정에서는 뒤의 데이터까지 인덱스를 모두 한 칸씩 뒤로 밀어야 한다.
최악의 경우 삽입해야 하는 위치를 찾기 위해 모든 인덱스를 탐색해야 한다.
시간 복잡도 : 삭제는 O(1), 삽입은 O(n)

(2) 우선순위 큐를 연결 리스트로 구현할 경우
우선순위가 높은 순서대로 연결 리스트 앞부분부터 연결시킨다.
우선도가 높은 데이터를 반환하는 것은 맨 앞의 인덱스를 바로 이용하는 것이다.
삽입과 마찬가지로 우선순위가 중간인 것의 삽입 과정에서는 뒤의 데이터까지 인덱스를 모두 한 칸씩 뒤로 밀어야 한다.
최악의 경우 모든 인덱스를 탐색해야 한다.
시간 복잡도 : 삭제는 O(1), 삽입은 O(n)

(3) 우선순위 큐를 힙으로 구현할 경우
삭제/삽입 과정에서 모두 부모/자식 간의 비교만 이루어진다.
이진 트리의 높이가 1개 증가할 때마다 저장 가능한 자료의 개수는 2배 증가하며, 비교 연산 횟수는 1회 증가한다.
시간 복잡도 : 삽입, 삭제 모두 O(logn)

그러므로 힙 방식이 최악의 경우에서 O(logN)을 보장하기 때문에 일반적으로 구현에 이용된다.

STL로 우선순위 큐 사용하기

헤더파일 및 생성자 형태

#include <queue>

//기본 생성자 형식 
priority_queue<int> q;

//내부 컨테이너 변경 : priority_queue < [Data Type], [Container Type] > 변수명;
priority_queue<int, <deque<int> > pq;

//정렬 기준 변경 : priority_queue< [Data Type], [Container Type], [정렬기준] > 변수명;
priority_queue<int, vector<int>, greater<int> > pq;

(정렬 기준을 주지 않으면 기본적으로 내림차순 정렬)

**멤버 함수** push(v) : v 원소 삽입 pop() : 우선순위가 높은 원소 삭제(값 반환 없음) top() : 맨 위에 있는 원소 반환(삭제 안함) empty() : 비어있는지 확인(리턴값 true/false) size() : 원소 개수 반환

기본적으로 큐 베이스여서 큐에 사용하는 함수와 동일.

참고 링크
https://chanhuiseok.github.io/posts/ds-4/
https://zoosso.tistory.com/993