우선순위 큐, Priority Queue

들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조

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

1. 배열
   삽입해야 하는 위치를 찾기 위해 최악의 경우 모든 인덱스를 탐색해야 함
   → 배열로 구현 시 시간 복잡도 : 삭제는 O(1), 삽입은 O(n)
   

2. 연결리스트
   삽입의 과정에서 그 위치를 찾아야 하므로 최악의 경우 모든 인덱스를 탐색하여야 함
   → 연결리스트로 구현 시 시간 복잡도 : 삭제는 O(1), 삽입은 O(n)
   

3. 힙
   힙의 경우 삭제나 삽입 과정에서 모두 부모와 자식 간의 비교만 계속 이루어짐
   이진 트리의 높이가 하나 증가할 때마다 저장 가능한 자료의 갯수는 2배 증가하며, 비교 연산 횟수는 1회 증가하므로 삭제나 삽입 모두 최악의 경우에는 O(log2n)
   → 힙으로 구현 시 시간 복잡도 : 삭제는 O(log2n), 삽입은 O(log2n)

4. 결론
   배열이나 연결 리스트가 삭제에서는 시간 복잡도의 우위(O(1)<O(log2n))지만, 삽입의 시간 복잡도가 힙 기반이 월등하기 때문에, 편차가 심한 배열과 연결리스트보다는 힙으로 구현하는 것이 유리
   ※ 힙으로 우선순위 큐를 구현할 때에는 노드에 저장된 값을 우선순위로 봄