[Data Structure] Priority Queue | 우선순위 큐

< Priority Queue > 

- an ADT for storing a collection of prioritized elements; the elements are referred to as values. 

(ADT - Abstract Data Type,

            this focuses on the behaviour of a data structure rather than on any implementation detail

            데이터 구조를 사용해 코드를 구현하는 것보다 데이터구조가 어떻게 작동하는지에 초점을 맞춘 것) 

 

- A key can be used to indicate the priority of a value( key: can be used to indicate the priority of a value) 

   Each entry in the P.Q is hence a pair of (key, value). 

 

Main methods of the Priority Queue ADT 

:  insert(key,value) : insert an entry with key k and value x into PQ, and return the entry storing them

   removeMin(): remove and returns the entry with the smallest key (smallest key indicates first priority) 

   Additional methods: min(): return the entry with the smallest key, but do not remove it 

                                       size(), isEmpty()

-  적용 예시: Auctions, Stock market 

 

=> 이러한 우선순위 큐를 구현하기 위해 the entry object, the comparator object가 필요하다. 

      

Entry ADT

: An entry in a priority queue is simply a key-value pair.

  -> Priority queues store entries to allow for efficient insertion and removal based on keys.

       that is, the entry in a priority queue is simply a key-value pair.