1
$\begingroup$

Does a priority queue Queue<K,V> always sort its elements based on the value of each element or its key?

I know than the priority in the queue is based on the key, and that the element with the highest priority has the minimal key (Correct me if I am wrong) But I am not sure about wether the pq sorts based on value.

$\endgroup$
2
  • 1
    $\begingroup$ This depends on the definition of Queue<K,V>, which should specify the semantics of the data structure. $\endgroup$ Dec 9, 2018 at 1:08
  • $\begingroup$ k(key) V(value) @YuvalFilmus $\endgroup$
    – user97496
    Dec 9, 2018 at 14:18

2 Answers 2

1
$\begingroup$

The definition of a priority queue is that elements will be dequeued in order of priority. The definition says nothing about the order of items of equal priority so an implementer can do anything, within reason, and still be justified in calling the resulting structure a priority queue.

$\endgroup$
0
$\begingroup$

Think about something like this:

 [(1,item1),(2,item2),(2,item3)]

    add (10,item4):

    [(1,item1),(2,item2),(2,item3),(4,item4)]

    dequeue
    [(2,item2),(2,item3),(4,item4)]

    add (1,item5)

    [(1,item5),(2,item2),(2,item3),(4,item4)]

The value would have nothing to do , the elements will be stored depending on its queue. (that was my final reasoning)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.