This discussion is archived
1 Reply Latest reply: Jan 7, 2011 5:11 AM by sabre150 RSS

Problem with PriorityBlockingQueue with comparator.

816202 Newbie
Currently Being Moderated
Hi All,

I am using PriorityBlockingQueue with custom comparator.
I can see that my elemnts are stored in order while entrying the data.
But when i take the value using take, it return the first elements and then again calls the comparator.
This again changes the order of elements.

Have anyone had similar issue or can guide me overcome it.
In comparator i am using a boolean field in comparator.

Regards
  • 1. Re: Problem with PriorityBlockingQueue with comparator.
    sabre150 Expert
    Currently Being Moderated
    user8726363 wrote:
    Hi All,

    I am using PriorityBlockingQueue with custom comparator.
    I can see that my elemnts are stored in order while entrying the data.
    But when i take the value using take, it return the first elements and then again calls the comparator.
    This again changes the order of elements.

    Have anyone had similar issue or can guide me overcome it.
    In comparator i am using a boolean field in comparator.
    I assume that the PriorityQueue is implemented as a 'heap' and internally a 'heap' stores the entries as a pseudo tree and not a linear list. When you remove the first element from the 'heap' the vacated slot has to be filled with the next highest priority value to be extracted. To do this it compares the next two entries (2 and 2+1) to see which need to be move to the first element. It then moves that element but it then needs to see which element to place in the newly vacated slot. To do this it compares the values at 2N and 2N+1 and moves the one with the highest priority into the vacated slot. This process is repeated recursively until there is no entry to place in the vacated slot.

    It means that each time a value is removed from the queue the comparator has to be called several time but on average Log2(number of entries) times. This logarithmic relationship also applies when an entry is added to the queue because the insert must find the slot to place an entry and then move the current value in that slot further up the pseudo tree.

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points