priority queue

Discussion in 'Java' started by Navhpf, Feb 23, 2004.

  1. Navhpf

    Navhpf Guest

    Hi all!

    I would need a kind of data structure that I cannot find in the JAVA
    API.
    It is a priority queue, allowing duplicates on the keys, but not on
    the elements.
    The kind of keys I need are of type float, and the elements would be 2
    or 3-dimensional integer arrays.
    As I understood it, Maps would not allow duplicate keys, and I cannot
    figure how to build an ordering of the data I use to build a Set (any
    Comparable implementation I can think of is not compatible with
    equals() ).

    Any help greatly appreciated,

    NaV
     
    Navhpf, Feb 23, 2004
    #1
    1. Advertising

  2. Hi!

    I use the BinaryHeap from http://jakarta.apache.org/commons/collections/
    for this cases.

    Regards,
    Thomas

    > Hi all!
    >
    > I would need a kind of data structure that I cannot find in the JAVA
    > API.
    > It is a priority queue, allowing duplicates on the keys, but not on
    > the elements.
    > The kind of keys I need are of type float, and the elements would be 2
    > or 3-dimensional integer arrays.
    > As I understood it, Maps would not allow duplicate keys, and I cannot
    > figure how to build an ordering of the data I use to build a Set (any
    > Comparable implementation I can think of is not compatible with
    > equals() ).
    >
    > Any help greatly appreciated,
    >
    > NaV
     
    Thomas Kreiss, Feb 23, 2004
    #2
    1. Advertising

  3. Navhpf <> scribbled the following:
    > Hi all!


    > I would need a kind of data structure that I cannot find in the JAVA
    > API.
    > It is a priority queue, allowing duplicates on the keys, but not on
    > the elements.
    > The kind of keys I need are of type float, and the elements would be 2
    > or 3-dimensional integer arrays.
    > As I understood it, Maps would not allow duplicate keys, and I cannot
    > figure how to build an ordering of the data I use to build a Set (any
    > Comparable implementation I can think of is not compatible with
    > equals() ).


    > Any help greatly appreciated,


    If I'm not altogether wrong, a priority queue which doesn't allow
    changing priorities while the object is still in the queue, can be made
    with several queues, one for each priority.
    Adding a new element takes O(1) time: put it in the queue that
    corresponds to its priority.
    Removing an element takes O(n) time: remove an element from the
    highest-priority queue you find having any elements left.

    --
    /-- Joona Palaste () ------------- Finland --------\
    \-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
    "'It can be easily shown that' means 'I saw a proof of this once (which I didn't
    understand) which I can no longer remember'."
    - A maths teacher
     
    Joona I Palaste, Feb 23, 2004
    #3
  4. Navhpf

    Navhpf Guest

    I currently use the JDSL ArrayHeap, but I can't figure out how to
    check for the presence of an element in the queue in an efficient way
    (I do it by fetching an iterator over all the Queue elements).
    This check is needed, as the JDSL PriorityQueue does not check for
    duplicated elements.

    Thanks for your answers, more input is welcome :)

    NaV
     
    Navhpf, Feb 23, 2004
    #4
    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. Aaron W. LaFramboise

    Stable priority queue

    Aaron W. LaFramboise, Apr 5, 2004, in forum: C++
    Replies:
    19
    Views:
    1,595
    Claudio Puviani
    Apr 7, 2004
  2. Jim Strathmeyer

    priority queue wrapper

    Jim Strathmeyer, Feb 25, 2005, in forum: C++
    Replies:
    1
    Views:
    578
    Dietmar Kuehl
    Feb 25, 2005
  3. Russell Warren

    Is Queue.Queue.queue.clear() thread-safe?

    Russell Warren, Jun 22, 2006, in forum: Python
    Replies:
    4
    Views:
    719
    Russell Warren
    Jun 27, 2006
  4. Marcel Müller
    Replies:
    3
    Views:
    591
    Marcel Müller
    Apr 27, 2009
  5. Kris
    Replies:
    0
    Views:
    529
Loading...

Share This Page