배열을 사용하는 방법
1. 정렬되지 않은 배열 사용
- 배열의 맨 끝에 새로운 요소를 추가
- 삽입 시의 시간 복잡도는 O(1)
- 삭제 시 우선 순위가 가장 높은 요소를 찾아야 함
- 정렬되어 있지 않으므로 배열의 처음부터 끝까지 모든 요소를 스캔
- 삭제 시의 시간 복잡도는 O(n)
- 요소 삭제 후, 삭제된 요소 뒤에 있는 요소들을 앞으로 이동시켜야 함
2. 정렬된 배열 사용
- 요소 삽입 시, 다른 요소와 값을 비교하여 적절한 삽입 위치를 결정
- 삽입 위치 뒤의 요소들을 이동시켜 빈자리를 만든 다음 삽입
- 삽입 시의 시간 복잡도는 O(n)
- 삭제 시 맨 앞 또는 맨 뒤의 요소를 삭제하면 됨
- 삭제의 시간 복잡도는 O(1)
연결 리스트를 사용하는 방법
- 배열을 사용한 방법과 유사
1. 정렬되지 않은 연결 리스트 사용
- 첫 번째 노드로 삽입하는 것이 유리
- 배열과 달리, 삽입 시 다른 노드를 이동할 필요 없이 포인터만 변경
- 삽입의 시간 복잡도는 O(1)
- 삭제 시, 포인터를 따라 모든 노드를 탐색
- 삭제의 시간 복잡도는 O(n)
2. 정렬된 연결 리스트 사용
- 우선 순위가 높은 요소가 앞에 위치하는 것이 유리
- 삽입 시 우선 순위 값을 기준으로 삽입위치를 탐색
- 삽입의 시간 복잡도는 O(n)
- 삭제 시 첫 번째 노드를 삭제
- 삭제의 시간 복잡도는 O(1)
히프를 사용하는 방법
히프(heap)
- 완전 이진 트리의 일종
- 우선순위 큐를 위해 특별히 만들어진 자료 구조
- 완전히 정렬된 것은 아니지만 전혀 정렬되지 않은 것도 아닌 상태 유지 → "느슨한 정렬 상태"
- 히프의 효율은 O(log₂n)
