.jpg)
📌 우선순위 큐란?
들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것
우선순위 큐를 구현하는 방법에는 3가지로 나누어집니다.
- 배열을 기반으로 구현하는 방법
- 연결리스트를 기반으로 구현하는 방법
힙(Heap)을 이용하는 방법
💡 우선순위 큐의 구현
✅ 배열을 기반으로 구현하는 방법
배열이나 연결리스트를 이용해서 우선 순위 큐를 구현하는 경우 간단하게 구현이 가능하다는 장점이 있습니다.
하지만 배열의 경우에는 여러가지 단점이 따릅니다.
데이터 삽입 및 삭제 과정에서 데이터를 한 칸씩 당기거나 밀어야하는 연산을 계속하여야합니다.
그리고 또 하나의 문제가 있습니다.
삽입의 위치를 찾기 위해 배열에 저장된
모든데이터와 우선순위를 비교해야 합니다.
이 경우는 우선순위가 가장 낮은 데이터를 저장하는 경우에 발생할 최악의 경우입니다.
✅ 연결리스트를 기반으로 구현하는 방법
문제점 : 삽입의 위치를 찾기 위해 첫번째 노드에서 부터 시작해 마지막 노드에 저장된 데이터와 우선순위 비교를 진행할지도 모릅니다.
이 경우는 데이터가 적은 경우에는 별 단점이 될 수는 없겠지만, 데이터가 많아질 때 노드의 수에 비례하여 비교할 대상이 증가하므로 성능이 저하됩니다.
그렇기 때문에 우선순위 큐는 주로 힙을 이용하여 구현하는 것이 일반적입니다.
힙의 경우 삭제나 삽입 과정에서 모두 부모와 자식 간의 비교만 계속해서 이루어집니다.
단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일합니다. (힙 정렬)
- 이러한 경우 시간 복잡도는
O(N logN)입니다.
✅ 힙을 기반으로 구현하는 방법
❗️ 힙에 대한 개념을 모른 다면 아래 페이지애서 확인 하세요
최소 힙 구성
- 상향식 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체합니다.
- 원소가 제거 되었을 때 힙 정렬에 의해
O(logN)의 시간 복잡도로 힙 성질을 유지 할 수 있습니다.
- 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 합니다.
❗️ 정리
우선 순위 큐는 배열, 리스트로 구현 하는 것 보다 힙을 사용하여 구현하는 것이 성능적 측면에서 좋고 보편적이다. 그 이유는 배열의 shift 연산, 연결리스트의 삭제 및 삽입 하는 경우 순회하는 시간복잡도에 비해 힙을 통한 삽입 삭제는 부모와 자식 간에만 비교 하기 때문에 시간 복잡도 O(NlogN) 으로 해결 할 수 있기 때문이다.
최소 힙 또는 최대 힙을 사용하여 구현 한다.
동작 원리
힙의 특성상 부모와 자식의 간의 비교를 통해서 우선 순위를 나누고힙 정렬을 통해 지속적으로 정리 해준다. 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 한다.
