기본기) 우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)

Queue에 우선순위에 대한 기능이 추가된 확장된 개념이다.

큐의 기본 메서드인 'Push',  'Pop', 'Top' 등등을 사용한다

Pop(가져오는 과정)에서 제일 먼저 들어온 데이터를 반환하지 않고

현재 우선순위 큐 내부에서 가장 우선순위가 높은 데이터를 반한 한다.

 

반응형

우선순위 큐는 보통(heap)이라는 자료구조로 구현되고 내부는 정렬을 기본적으로 처리된다.

'모든 정점은 자신의 자식보다 우선순위가 높다'.

시간 복잡도는O(logN)가 되고 내부는 역시 이진트리로 되어있다.

 

★☆☆☆☆