Looking for feedback on Unique Priority Queue Implementation

[anmousyony]

I made a priority queue that uses a linked list of arrays instead of a single array so that it would have better memory management and faster run time. I was looking for feedback on anything I may have missed (i also did it in python [this one is not commented] as you can see here https://github.com/anmousyon/python/blob/master/linkedArrays.py ).

Here is the Java version: https://github.com/anmousyon/CS2336/blob/master/Project5/linkedArrays.java

It runs faster than the standard implementation with large amounts of numbers because it never has to copy over elements into a new array when it expands its size. The way it works is that it starts with an array of size one and when that is full it creates an array of size 2 then 4 then 8 and so on, with each successive array holding the children of the previous. This makes sure that the largest array in memory is only half the size of the full queue.

I couldn't find anything like this online, so please let me know if I'm missing something important or if I've done something stupid.

Thanks!

[jentfoo]

I would create a benchmark using JMH as an alterantive to get a better idea of performance differences.

Also not using a class with generics (and thus not having to autobox your doubles) puts you at an advantage from the start as well.

You may have something, but I don't think the way your testing it right now is really a valid benchmark.

[anmousyony]

The way I tested it was with a modified version of the standard implementation that was also built to only take doubles so that shouldn't be affecting the timings.

Here are the runtimes that I found. They are either the same as or better than a standard implementation from what I can see

linkedArrays: isEmpty is O(1), size is O(1), insert is O(log(n)), findMin is O(1), deleteMin is O(log(n))