Priority Queue

dragonappear·2021년 3월 26일
0

Data Structure

목록 보기
2/4

Prioriy Queue:

일반적인 큐는 FIFO구조이다.

즉, 어떠한 조건없이 먼저 들어온 데이터가 먼저 나가는 구조이다.

하지만, 우선순위 큐는 들어간 순서에 상관없이 우선순위 높은 데이터가 먼저 나오는것을 말한다.

우선순위 큐는 힙이라는 자료구조를 가지고 구현한다.

우선순위 큐는 배열이나 연결리스트로 구현하지 않는 이유?

1) 만일 배열로 구현한다면 우선순위가 높은 순서대로 배열의 가장 앞부분부터 넣는다면, 우선순위가 높은 데이터를 반환하는 것은 맨 앞의 인덱스를 이용하면 되기 때문에 어렵지 않다.

하지만 우선순위가 중간인 것이 들어가야하는 삽입과정에서는 뒤의 데이터까지 인덱스를 모두 한칸씩 뒤로 밀어야하는 단점이 있다.

최악의 경우 삽입해야 하는 위치를 찾기위해 모든 인덱스를 탐색해야 한다.

즉 이때의 삽입 시간복잡도는 O(n)이 되고, 삭제는 O(1)이 된다.

2) 만약 연결리스트로 구현한다면 이또한 우선순위가 높은 순서대로 연결시키면 우선순위가 높은 데이터의 반환은 배열과 마찬가지로 쉽다.

하지만 연결리스트의 삽입 과정 또한 배열과 마찬가지로 그 위치를 찾아야 한다. 최악의 경우 맨 끝까지 탐색해야 한다.

즉 이때의 삽입 시간복잡도는 O(n)이 되고, 삭제는 O(1)이 된다.

3) 힙기반으로 구현한다고 가정하면 힙의 삭제나 삽입 과정에서 모두 부모와 자식간의 비교만 이루어진다.

즉, 이진트리의 높이가 하나 증가할때마다 저장 가능한 자료의 개수는 2배 증가하면, 비교연산 횟수는 1회 증가한다.

즉 이때의 삽입 시간복잡도는 O(lg(n))이 되고, 삭제는 O(lg(n))이 된다.


참고:

링크텍스트

0개의 댓글