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$
  • 1
    $\begingroup$ This depends on the definition of Queue<K,V>, which should specify the semantics of the data structure. $\endgroup$ – Yuval Filmus Dec 9 '18 at 1:08
  • $\begingroup$ k(key) V(value) @YuvalFilmus $\endgroup$ – Pablo Biedma Dec 9 '18 at 14:18
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, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.