[자료구조] 우선순위 큐
까먹지 않으려고 기록하는 게시물
예전 게시물에서 우선 순위 큐에 대해 기록한 적이 있지만 공부하다 보니 추가할 내용이 생겼다.
우선순위 큐 혼공 기록 스타트!
우선순위 큐의 구현 방법
1. 배열을 기반으로 구현하는 방법
- 방법: 데이터의 우선순위가 높을수록 배열의 앞쪽에 데이터를 위치시킴
- 단점:
(1) 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 해줘야 함
(2) 삽입할 위치를 찾기 위해 배열 내 저장된 데이터와 하나하나 비교 연산을 해줘야 함 (우선순위가 가장 낮은 데이터를 저장하는 경우에는 배열의 모든 데이터와 다 비교해줘야 함)
- 데이터 삽입 시간 복잡도: O(n)
→ 우선순위가 낮은 데이터를 삽입할 경우 배열의 모든 데이터와 비교 연산을 수행함
- 데이터 삭제 시간 복잡도: O(1)
→ 배열의 맨 앞에 위치한 데이터만 삭제해주면 됨
2. 연결 리스트를 기반으로 구현하는 방법
단점:
(1) 삽입할 위치를 찾기 위해 첫 번째 노드에서부터 시작하여 마지막 노드에 저장된 데이터와 우선순위의 비교를 진행해야 할 수 있음
- 데이터 삽입 시간 복잡도: O(n)
- 데이터 삭제 시간 복잡도: O(1)
3. 힙을 이용하는 방법
min heapify는 아래 첨부한 gif 파일을 보면 쉽게 이해할 수 있다.
힙을 이용하여 구현된 우선순위 큐에서의 데이터 삽입:
최소 힙의 형태를 가지는 우선순위 큐가 일단 구현되었다고 치자. 그러고 나서 새로운 데이터가 삽입되었다고 가정하자. 새로운 데이터는 우선순위가 제일 낮다는 가정 하에서 마지막 위치에 저장이 되고, 부모 노드와 우선순위를 비교해서 필요시 위치를 바꿔준다. 그러고 나서 계속해서 부모 노드와 비교하며 제자리를 찾아간다.
힙을 이용하여 구현된 우선순위 큐에서의 데이터 삽입:
우선순위 큐에서의 데이터 삭제는 가장 높은 우선순위를 가진 데이터를 삭제한다는 것을 뜻한다. 그렇게 되면 루트 노드를 삭제해줘야 하는데 루트 노드를 삭제한 후에도 힙의 구조를 가져야 한다는 중요한 점을 간과해서는 안 된다. 그렇다면 힙에서 루트 노드를 삭제한 다음 이 부분을 어떻게 채워야 할까?
→ Solution: 마지막 노드를 루트 노드의 자리로 옮긴 다음 자식 노드와의비교를 통해서 제자리를 찾아가게 한다.
- 데이터 삽입 시간 복잡도: O (log2n)
- 데이터 삭제 시간 복잡도: O(log2n)
→ 힙은 완전 이진 트리이기 때문에 힙에 저장할 수 있는 데이터의 수는 트리의 높이가 하나 늘 때마다 두배씩 증가하게 됨. 따라서 데이터의 수가 두 배 늘어날 때마다 비교 연산의 횟수는 1회 증가함