우선순위 큐

• 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 입니다.
• 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용합니다.
• 예) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우.

각각의 물건정보를 가치데이터와 함께 우선순위 큐에 넣었다가 꺼낼때에는 항상 가치가 높은 값부터 꺼내게 되는 구조.

 

 

우선순위 큐를 구현하는 방법은 다양합니다.

1. 단순히 리스트를 이용하여 구현할 수 있습니다.
2. 힙(heap)을 이용하여 구현할 수 있습니다.

데이터의 개수가 N개일 때, 구현 방식에 따라서 시간 복잡도를 비교한 내용은 다음과 같습니다.

 

단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일합니다.(힙 정렬)

이경우에 시간 복잡도는 O(NlogN)입니다.

 

따라서 Heap으로 구현하는 것이 시간 복잡도 면에서 유리하다고 할 수 있습니다.

 

 

Heap의 특징

• 힙은 완전 이진 트리 자료구조의 일종입니다.
• 힙에서는 항상 루트 노드를 제거합니다.
• 최소힙(min heap) 과 최대 힙(max heap)이 있다.

1. 최소 힙
   1. 루트 노드가 가장 작은값을 가집니다.
   2. 따라서 값이 작은 데이터가 우선적으로 제거 됩니다.
2. 최대 힙
   1. 루트 노드가 가장 큰 값을 가집니다.
   2. 따라서 값이 큰 데이터가 우선적으로 제거 됩니다.

 

C++은 기본적으로 maxheap구조이다.