우선순위 큐(Priority Queue)

Priority Queue

• 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
• 데이터를 우선순위에 따라 처리하고 싶을 때 사용
• 구현하는 방법
  1. 단순히 리스트를 이용하여 구현 가능
  2. 힙(heap)을 이용하여 구현 가능
• 데이터 개수가 N개일 때, 구현 방식에 따라서 시간 복잡도 비교 가능
  

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트	O(1) : 단순히 삽입만 하면 됨	O(N) : 우선순위가 높은 값을 찾아야 하므로 선형적인 탐색 필요
힙	O(logN)	O(logN)

 

• 힙의 특징
  - 힙은 완전 이진 트리구조의 일종
  - 힙에서는 항상 루트 노드를 제거
  - 최소 힙 : 루트 노드가 가장 작은 값을 가지며, 값이 작은 데이터가 우선적으로 제거
  - 최대 힙 : 루트 노드가 가장 큰 값을 가지며, 값이 큰 데이터가 우선적으로 제거
• 힙에 새로운 원소가 삽입될 때
  - O(logN)의 시간 복잡도로 힙 성질을 유지 : 새로운 값이 들어왔을 때 부모 노드와 값 비교만 해주면 됨! 예시를 보면 2라는 값이 들어왔을 때 단 두번만으로도 정렬이 완성되는 것이 특징
  

• 힙에서 원소가 제거될 때 
  - 최악의 시간복잡도에서도 O(log2)의 시간복잡도를 가짐
  - 원소를 제거할 때는 가장 마지막 노드가 루트 노드에 위치하도록 함
  - 이후에 루트 노드와 하향식으로 값을 비교하여 더 작은 값이 루트 노드에 올 수 있도록 Heapify()를 진행