-1

I've tried looking at many websites, such as:

How do I use a PriorityQueue?

Java PriorityQueue with fixed size

but they don't seem to answer my question.

More specifically, I'm trying to implement a custom Priority Queue where I can only have a zero/1 argument constructor that can be either zero/capacity/p-queueobject. Is this possible considering the thread

How do I use a PriorityQueue?

talks about a 2-arg constructor (capacity, comparator)?

Added: Are the values of P-Queue always stored and retrieved as a binary tree? Wouldn't they always be sorted already then? e.g. [5, 6, 6, 64, 9]

Community
  • 1
  • 1
user3511965
  • 195
  • 1
  • 3
  • 9
  • 1
    You might take a look at http://stackoverflow.com/questions/683041/java-how-do-i-use-a-priorityqueue – jeroen_de_schutter May 08 '14 at 06:19
  • 1
    The queue **is** the heap. They are not two distinct things. – monocell May 08 '14 at 06:20
  • @jeroen_de_schutter Thanks. I did look at that but I still have some questions. For example, the top answer focused on a 2-arg constructor, but is it possible to just use a 1-arg constructor where the argument is the same object type (P-Queue) instead of using a comparator object? – user3511965 May 08 '14 at 06:28
  • You don't need the comparator if your queue objects implements comparable. For this kind of questions the javadocs are a great resource: http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html – monocell May 08 '14 at 06:33

1 Answers1

1

Regarding constructors

PriorityQueue already have a zero argument constructor. You can see this yourself easily if you read the javadocs. Whether or not this suits your purpose I can't say. It does require that you use a type that implements comparable (e.g. String, Integer) otherwise the queue will have no way of knowing how to order the elements.

capacity in the case of PriorityQueue is not a max capacity, but just a hint about how many elements you think will be in the queue at the same time. It has only performance implications, the semantics of they queue are completely independent of this.

Storage and retrieval semantics

The values are stored (inserted) in any order but are retrieved in order. That is the point of a priority queue. A list that is automatically sorted every time you append to it will give you exactly the same semantics as javas PriorityQueue. The list implementation would be very inefficient thought, so that's why you use a heap instead.

I'm not sure if this is a response to what you are asking, so if it's not please clarify what you are confused about.

Community
  • 1
  • 1
monocell
  • 1,411
  • 10
  • 14
  • Thanks. My task is to implement P-Queue with 0/1/2 args for a constructor so I guess I'll have to implement them in a variety of ways. For the storage and retrieval part, I see that P-Queue adds elements to the back of the list, but when I offer(element), it somehow reorders the arrangement of the list after removing that element. Is this how P-Queue works? – user3511965 May 08 '14 at 17:19
  • It doesn't work with a list at all, but the semantics are the same as reordering the list after each insert, not after each poll. I think offer and add are synonyms in the case of priority queue. – monocell May 08 '14 at 17:57
  • If your task is to implement a priority queue perhaps you shouldn't think to much about how the standard one is implemented. – monocell May 08 '14 at 17:58
  • Okay, maybe I should just ask, which is the best way to implement add/remove/peek? Should add() sort the array immediately so remove can remove the first element, or should add() just add it to the front and remove/peek will traverse to find the highest priority element? Which one is the best way to do it? – user3511965 May 09 '14 at 00:10
  • Neither, the best way is to use a heap. Furthermore, if this is something like a school assignment then I doubt a sorting list solution will be accepted. – monocell May 09 '14 at 05:12