8.1 우선순위 큐 추상 자료형
우선순위 큐의 소개
우선순위 큐(priority queue): 데이터들이 우선순뤼를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 됨
자료구조삭제되는 요소
스택 | 가장 최근에 들어온 데이터 |
큐 | 가장 먼저 들어온 데이터 |
우선순위 큐 | 가장 우선순위가 높은 데이터 |
우선순위 큐의 추상 자료형
<ADT 8.1.1> 우선순위 큐
객체: n개의 element 형의 우선순위를 가진 요소들의 모임
연산:
create() ::= 우선순위 큐를 생성
init(q) ::= 우선순위 큐 q를 초기화
is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
is_full(q) ::= 우선순위 큐 q가 가득찼는지 검사
insert(q,x) ::= 우선순위 큐 q에 요소 x를 추가
delete(q) ::= 우선순위 큐 q로부터 가장 우선순위가 높은 요소를 삭제하고 이 요소를 반환
find(q) ::= 우선순위가 가장 높은 요소를 반환
Quiz
- 왜 우선순위 큐가 가장 일반적인 큐라고 할 수 있는가?
-> 스택이나 큐도 우선순위 큐를 사용하여 얼마든지 구현할 수 있기 때문 - 스택이나 큐도 우선순위 큐로 구현할 수 있는가?
-> 적절한 우선순위만 부여하면 우선순위 큐는 스택이나 큐로 동작함. 데이터가 들어온 시각을 우선순위로 잡으면 일반적인 큐 처럼 동작
8.2 우선순위 큐의 구현 방법
배열을 사용하는 방법
- 정렬이 안된 배열일 때
- 삽입 => 기존의 요소들의 맨 끝에 붙이면 됨(시간복잡도 )
- 삭제(가장 우선순위가 높은 요소를 삭제) => 처음부터 끝까지 모든 요소들을 스캔해야 삭제 가능(시간복잡도 ), 삭제 후 뒤에 있는 요소를 앞으로 이동시켜야 하는 부담이 있음
- 정렬이 되어 있는 배열일 때
- 삽입 => 일일이 다른 요소와 비교하여 우선순위에 따라 삽입 위치(순차 탐색, 이진 탐색)를 결정해야 함,그 후 삽입 위치 뒤에 있는 요소들을 이동시켜서 빈자리를 만든 다음 삽입해야 함(시간복잡도 )
- 삭제 => 숫자 높은 것이 우선순위가 높다고 가정할 때 맨 뒤에 위치한 요소를 삭제하면 됨(시간복잡도 )
연결 리스트를 사용하는 방법
- 정렬이 안된 연결 리스트일 때
- 삽입 => 첫 번째 노드로 삽입시키는 것이 유리, 배열과 달리 다른 노드를 이동할 필요 없이 포인터만 변경하면 됨(시간복잡도 )
- 삭제 => 포인터를 따라 모든 노드를 뒤져봐야 함(시간복잡도 )
- 정렬된 연결 리스트일 때(우선순위가 높은 요소가 앞에 있는 것이 유리)
- 삽입 => 우선순위 값을 기준으로 갑입 위치를 찾아 삽입(시간복잡도 )
- 삭제 -> 첫 번째 노드를 삭제하면 됨(시간복잡도 )
힙을 사용하는 방법
힙(heap): 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조, 반정렬 상태를 유지
'자료구조와 알고리즘 ft. 수업 > 자료구조 정리' 카테고리의 다른 글
그래프 I (0) | 2023.05.14 |
---|---|
힙 (1) | 2023.05.14 |
2. 균형 이진 탐색 트리 (0) | 2023.05.11 |
10. 정렬 알고리즘의 비교 (0) | 2023.04.01 |
9. 기 수 정렬 (0) | 2023.04.01 |