Results 1 to 6 of 6
Like Tree1Likes
  • 1 Post By pbrockway2

Thread: Priority Queue

  1. #1
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default Priority Queue

    I have to write an ADT specification for a priority queue. The methods that I am thinking that should be included are:

    -getHighPriority() - returns the highest priority item in the list.
    -size() returns the size of the priority queue.
    -isEmpty() boolean to tell if the queue is empty or not.
    -add(item E, priority p) - will add the item to the list, and assign a priority to it
    -add(item E) will add the item to the queue, and assign it a priority that is 1 behind the item with the lowest priority contained in the queue.


    Am I overlooking important methods? Also, I looked at the java PriorityQueue class, and I do not see any methods that seem to allow you to assign a priority to an item that you add, or is that option not available? Adding an item to the queue automatically assigns the priority?

  2. #2
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    25

    Default

    The priority is based on properties of the objects themselves, either by having the class of the objects held implement Comparable or by using a Comparator. The tutorials will tell you how this is done.

  3. #3
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    One way of seeing what should go into a priority queue ADT is to look at particular implementations. Java has one in the form of a PriorityQueue.

    Where you have getHighPriority() the collections framework has peek() and poll() - the difference is whether the object is removed from the collection: it is returned in either case. And so on for the other methdos you describe.

    Some of the PriorityQueue methods make sense because they are part of a more general collection framework. (I am thinking of methods like addAll() which PriorityQueue shares with other types of queue.)

    One method you have - add(item E, priority p) - goes "against the grain" of how Java's PriorityQueue works. "The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used." This is the point Fubarable was making. The priority is somehow implicit in the objects themselves.

    -----

    ADT's are, in the nature of things, abstract. How you implement (or in detail how you *define* them) will depend on the use you intend to make of them: the framework of which they are part, the specific situations in which they will used (as actual code), whether they will be objects about which you intend to derive formal results.
    Fubarable likes this.

  4. #4
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    25

    Default

    Ah, I missed the ADT/Abstract Data Type bit at the beginning of the OP's post. Please ignore my response and go with pbrockways.

  5. #5
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    I think I understand your explanations. So in developing the ADT specification, would it be the same as writing an interface for a PriorityQueue?

  6. #6
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    PriorityQueue is actually a class (ie it has an implementation). But, yes, an interface is just a way - using Java syntax - of writing a specification.

Similar Threads

  1. Priority Queue with explicit priority
    By lsk in forum Advanced Java
    Replies: 4
    Last Post: 06-10-2011, 07:16 PM
  2. Priority Queue
    By Suende in forum New To Java
    Replies: 19
    Last Post: 04-25-2011, 08:46 AM
  3. Priority Queue experts needed !!!
    By niu_niu in forum New To Java
    Replies: 48
    Last Post: 06-11-2010, 08:48 AM
  4. Priority Queue Question
    By Taz_84 in forum New To Java
    Replies: 0
    Last Post: 01-29-2009, 03:23 AM
  5. How to implement Priority queue with Java
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-12-2008, 08:49 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •