I guess PriorityBlockingDeque wasn't high on the priority list..

hi there, What is the license for your software ? Thank you, BR, ~A

Which software? The collections library?

I think I understand what you mean, and I've added a license section above the code. I don't know how that slipped out... Basically it's the new BSD license.

PriorityQueue is implemented as a heap, which can be constructed in linear time (via bottom-up heap construction), which is much less expensive than sorting. However, if a dequeue is implemented upon a heap, the max (getFirst) can be retrieved in O(1) time, but there is no efficient way to get the min (getLast). Maybe a "PriorityDequeue" is actually a SortedList ?

What you say is true - a heap is unusable for retrieving the last element. I don't understand your suggestion - I do not know of a SortedList interface/implementation in the JDK.. Perhaps you meant SortedSet? And if so, NavigableSet, which I use, is an extension of that interface. The unfortunate thing about the PriorityBlockingDeque implementation of mine is that it doesn't allow duplicate values, as that's the primary constraint a Set has.

I guess there is no need for a SortedList interface. A sorted List can be easily attained via Collections.sort(List), and subsequently maintained via ordered insertion via Collections.binarySearch(List).

I disagree. This obviously works fine but it lacks two main features of actually having a SortedList interface: 1. There is no abstraction from the List's user, where he can just count on the items to be sorted. As a user of a framework, I want to be able to call "add" on a List interface, and later on an internal implementation would know this is sorted and use it for its own needs - Otherwise, I need to abstract it myself when exposing the List in my classes. 2. There is no ability to implement the list in a way that is better suited for sorting, i.e. using data structures that are better for the task. Just like that a Set interface can be implemented using a hash table, but to reach a SortedSet you need a different implementation - each is more efficient for what the interface needs to provide.

The reason there is no SortedList is in the List's documentation:

[A list is] an ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.

A SortedList would break this rule, and methods such as "add(int, Object)" would have no meaning.

So, since I seem to be contradicting myself in the last two comments, let me reiterate: An interface that encapsulates SortedList would have been important even if you can achieve the same goal with java.util.Collections methods. The reason is for abstraction and for straight definition, also for additional methods that might be required such as retrieving the used Comparator (such as in SortedSet). However, since List as an interface does not allow automatic sorting by definition, this seems (to me at least) to be the reason why this type of List is missing. On the other hand, PriorityDeque is not a SortedList as well because it lacks features of a List - such as retrieving elements at a certain index etc. On a different note, implementing PriorityDeque using a List and Collections methods would probably prove to be better conceptually, if not in performance, since it will permit duplicate values, something that NavigableSet does not. What do you think?

>implementing PriorityDeque using a List and >Collections methods would probably prove to be >better conceptually, if not in performance, since it >will permit duplicate values, something that >NavigableSet does not. >What do you think? That's basically what I was trying to suggest :)

I've created a test for it, and sure enough it fails with duplicate values; I've re-implemented it, this time using a LinkedList with a Collections.sort call when adding elements, and now it accepts duplicates. I've checked it in so it should be available now.

>with a Collections.sort call when adding elements There is no need to sort when adding elements. Sorting is necessary only when the list is initially constructed. Subsequently adding elements only requires a binary search + insert. That will yield ln(n) instead of n*ln(n) time.

You're right. I've changed it and checked it in.

I havn't looks at how LinkedList and Collection.sort are implemented in detail, but doing a binary search on a linked list seems to be a bad idea to me. Accessing index i takes i steps on a linked list, so a binary search would be in O(n * log(n)). Simple linear scanning would be faster (O(n)). It's kind of sad that ListIterator doesn't have an insert method - that would avoid the issue that you have to scan twice: once iterating over the list to find the right place to insert your element, then again to actually insert it, using add(int, Object). Anyway, by not doing a binary search but simply scanning for the place to insert the new item, i believe you can bring the complexity of add from O(n*log(n)) down to O(n). Still not great, but better...

You're right, however, I could always change it to ArrayList and get it over with - receive the log(n) efficiency on one hand but might stumble upon bad efficiency during add() methods that exceed the size. For that case, I could probably use the capacity to create the list at the right size right from the start (unless it's Integer.MAX_VALUE, of course).

Using an ArrayList would give you O(log(n)) complexity for add, but means O(n) complexity for removing the head of the queue (at least I think so - again, I have not looked at how ArrayList is implemented, exactly). So, assuming an equal total number of add and remove/poll operations, the options appear to be: Use a LinkedList, with O(n) for add and O(1) for remove, giving you an amortized complexity of O(n), or using an ArrayList with O(log(n)) for add and O(n) for remove/poll, again giving you an amortized complexity of O(n), but with more overhead in practice (because you need n+log(n) steps and, as you mentioned, possibly for growing the array). It would be interesting to run a benchmark to see which one is actually better for a "practical" size of the queue and number of add/remove operations.

What you said brought up a memory and after careful checking I remembered why I didn't use ArrayList in the first place (as it's obviously the more efficient one) - it doesn't have pollFirst and pollLast functionality at all, as it doesn't implement the Deque interface, unlike LinkedList. However, a Deque implementation using a ring-array is definitely possible, and I'm sure there's a ring-array implementation somewhere out there to be used instead of re-writing it. However, as to what you said, take a look at the Collections.sort documentation:

This method runs in log(n) time for a "random access" list (which provides near-constant-time positional access). If the specified list does not implement the RandomAccess interface and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons.

If I understand this correctly, this verifies what you said.

Hah, no it doesn't confirm what I said. I should have read the docs carefully. Collections.sort is smarter than i thought - while a naive binary search on a LinkedList would be O(n * log(n)), Collections.sort does it in n steps with only log(n) comparisons, as opposed to n steps and n comparisons for the linear scan i suggested. I guess this is made possible by the fact that ListIterator can move both ways. Another mistake I made is: ListIterator does haven an insert method (add). Sorry. So, as it turns out, your LinkedList/Collections.sort based implementation seems to be optimal (or at least, slightly better than what I suggested), and I should read the documentation more closely :) Thanks for this great blog, btw.

Heh, and I read them carefully but misunderstand what they mean. Well, anyway, that's sorted out. Thanks for the input!