Get the tail of a PriorityQueue?

Discussion in 'Java' started by jimi_usenet@hotmail.com, Feb 16, 2006.

  1. Guest

    Hi all,

    I have a class MaxCapacityPriorityQueue that extends
    java.util.PriorityQueue, and has the added functionallity that it has a
    maximum capacity, and it doesn't grow above this limit (when the queue
    is full and an additional object is added, it removes the last object
    in the queue, ie the "smallest" one according to the comparator). All
    this works fine.
    But now I would like to check the "biggest" (according to the
    comparator) object in the queue, ie the one in the tail. But there is
    no such function. I only see peek() and poll() wich gives me the
    *head*.
    Is there a better priority queue out there, that has this
    functionallity? Or is there a way for me to add it in my subclass of
    PriorityQueue? The internal Object[] queue in this class is private, so
    I can't access it directly.
     
    , Feb 16, 2006
    #1
    1. Advertising

  2. Since a PriorityQueue offers fast access to the lowest element, you
    will want to use a reverseOrder comparator for this task (See
    java.util.Collections). However, part of the beauty of Priority Queues
    is that they can be very efficiently implemented using a heap
    (described in most textbooks), which offers no real guarantees other
    then being easily able to find and maintain the minimum element.

    Since the very good performance in the case of the findMin operation
    comes at the price of a less then totally structured ordering, you can
    either use another queue implementation which uses a sorted list as
    backing structure, or try to muck around with re-implementing a heap
    which seeks out a maximum (in your case: Minimum) element when it has
    no more space. Note that this is potentially as expensive as keeping a
    sorted list, since an "overflow insert" will take as long as the number
    of elements in the PQ, instead of only log(n).
     
    Stefan Schulz, Feb 16, 2006
    #2
    1. Advertising

  3. Chris Uppal Guest

    wrote:

    > I have a class MaxCapacityPriorityQueue that extends
    > java.util.PriorityQueue, and has the added functionallity that it has a
    > maximum capacity, and it doesn't grow above this limit (when the queue
    > is full and an additional object is added, it removes the last object
    > in the queue, ie the "smallest" one according to the comparator). All
    > this works fine.
    > But now I would like to check the "biggest" (according to the
    > comparator) object in the queue, ie the one in the tail. But there is
    > no such function


    I think you may be misunderstanding the priority heap data-structure (of which
    java.util.PQ is an implementation). The point is that it gains efficiency by
    /not/ keeping a completely sorted list of all the elements. So, although it
    can efficiently find the first (least) element in the queue it does not know
    which element is the last (greatest).

    You might be able to get the effect you want by using two PQs, with opposite
    comparators. I'm not sure whether that would have any efficiency benefits over
    just keeping a completely sorted list of elements internally.

    -- chris
     
    Chris Uppal, Feb 16, 2006
    #3
  4. Not really, since any element removed from one by poll() would need to
    be removed from the other, leading to an iteration over the entire
    second heap.
     
    Stefan Schulz, Feb 16, 2006
    #4
  5. Chris Uppal Guest

    Stefan Schulz wrote:

    > Not really,


    Not really what ?


    > [...] any element removed from one by poll() would need to
    > be removed from the other, leading to an iteration over the entire
    > second heap.


    Good point.

    Inserting into a sorted array would be O(N) too (in element moves, not
    comparisons).

    Obvious solution[*]: use a java.io.TreeSet.

    -- chris

    [*] In retrospect.
     
    Chris Uppal, Feb 16, 2006
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Frank D. Greco

    Swing, tail -f and threading

    Frank D. Greco, May 29, 2004, in forum: Java
    Replies:
    3
    Views:
    1,074
    Thomas Weidenfeller
    Jun 2, 2004
  2. Twisted
    Replies:
    3
    Views:
    810
    cloud
    Oct 14, 2012
  3. Twisted

    NPE in PriorityQueue.poll()

    Twisted, Nov 16, 2006, in forum: Java
    Replies:
    30
    Views:
    1,715
    Andreas Leitgeb
    Nov 20, 2006
  4. Just Another Victim of the Ambient Morality

    How do you get the tail end of a string?

    Just Another Victim of the Ambient Morality, Oct 30, 2009, in forum: Ruby
    Replies:
    52
    Views:
    1,261
    Robert Klemme
    Dec 1, 2009
  5. Terry Michaels

    Tail Call Optimization (Tail Recursion)

    Terry Michaels, Apr 18, 2011, in forum: Ruby
    Replies:
    16
    Views:
    316
    Robert Klemme
    Apr 20, 2011
Loading...

Share This Page