우선순위 큐란 ?
우선순위의 개념을 큐에 도입한 자료구조
- 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 나감
- 힙을 이용하여 구현하는 것이 가장 효율적
- 스택은 LIFO, 큐는 FIFO
사용 예시
시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산
우선순위 큐는 배열, 연결리스트, 힙으로 구현 (힙으로 구현이 가장 효율적!)
우선순위 큐를 배열로 구현할 경우,
- 데이터 삽입 및 삭제 과정에서 데이터를 한 칸씩 당기거나 밀어야 하는 연산을 계속 해야 한다.
- 삽입의 위치를 찾기 위해 저장된 모든 데이터와 우선순위를 비교해야 한다.
연결리스트로 구현할 경우,
- 삽입의 위치를 찾기 위해 첫번째 노드에서부터 시작해 마지막 노드에 저장된 데이터와 우선순위 비교를 진행할지도 모른다.
-> 데이터가 많아질 때, 노드의 수에 비례에 비교할 대상이 증가하므로 성능의 저하 발생
따라서, 우선순위 큐는 힙을 이용하여 구현한다.
힙 → 삽입 : O(logn) , 삭제 : O(logn)
Hello World!