In general, there is no good way to force your objects in the queue to occupy a contiguous chunk of memory. There are, however, some techniques that are suitable for special cases.
At a high level, the techniques involve using byte arrays and 'serializing' data to and from the array. This is actually quite effective if you are storing very simple objects. For example, if you are storing a bunch of 2D points + weights, you can simply write byte equivalent of the weight, x-coordinate, y-coordinate.
The problem at this point, of course, is in allocating instances while peeking/popping. You can avoid this by using a callback.
Note that even in cases where the object being stored itself is complex, using a technique similar to this where you keep one array for the weights and a separate array of references for the actual objects allows you to avoid following the object reference until absolutely necessary.
Going back to the approach for storing simple immutable value-type, here's an incomplete sketch of what you could do:
abstract class LowLevelPQ<T> {
interface DataHandler<R, T> {
R handle(byte[] source, int startLoc);
}
LowLevelPQ(int entryByteSize) { ... }
abstract encode(T element, byte[] target, int startLoc);
abstract T decode(byte[] source, int startLoc);
abstract int compare(byte[] data, int startLoc1, int startLoc2);
abstract <R> R peek(DataHandler<R, T> handler) { ... }
abstract <R> R pop(DataHandler<R, T> handler) { ... }
}
class WeightedPoint {
WeightedPoint(int weight, double x, double y) { ... }
double weight() { ... }
double x() { ... }
...
}
class WeightedPointPQ extends LowLevelPQ<WeightedPoint> {
WeightedPointPQ() {
super(4 + 8 + 8); // int,double,double
}
int compare(byte[] data, int startLoc1, int startLoc2) {
// relies on Java's big endian-ness
for (int i = 0; i < 4; ++i) {
int v1 = 0xFF & (int) data[startLoc1];
int v2 = 0xFF & (int) data[startLoc2];
if (v1 < v2) { return -1; }
if (v1 > v2) { return 1; }
}
return 0;
}
...
}
