# For Large number of nodes Min Heap implementation Dijkstra's Algorithm throwing OutOfMemoryError Exception

I am implementing Dijkstra's Algorithm using Min Heap to speed up the code. For small number of nodes, the code is really running very fast. But for large number of nodes, my code is throwing java.lang.OutOfMemoryError: Java heap space exception. My Min heap implementation is based on the code, given here in C++. I changed this code into Java. Below is my min heap code (i am not putting Dijkstra's Algorithm code. As it is same as described in the above link.)-

public class Heap {
private static int[] data;
private static int[] index;
public static int[] cost;
public static boolean[] eval;
private static int size;

public Heap(int s) {
data = new int[s];
index = new int[s];
cost = new int[s];
eval = new boolean[s];
}

public void init(int s) {
for (int i = 0; i < s; i++) {
index[i] = -1;
eval[i] = false;
}
size = 0;
}

public boolean isEmpty() {
return (size == 0);
}

private void shiftUp(int i) {
int j;
while (i > 0) {
j = (i - 1) / 2;
if (cost[data[i]] < cost[data[j]]) {

int temp = index[data[i]];
index[data[i]] = index[data[j]];
index[data[j]] = temp;

temp = data[i];
data[i] = data[j];
data[j] = temp;
i = j;
} else
break;
}
}

private void shiftDown(int i) {
int j, k;
while (2 * i + 1 < size) {
j = 2 * i + 1;
k = j + 1;
if (k < size && cost[data[k]] < cost[data[j]]
&& cost[data[k]] < cost[data[i]]) {

int temp = index[data[k]];
index[data[k]] = index[data[i]];
index[data[i]] = temp;

temp = data[k];
data[k] = data[i];
data[i] = temp;

i = k;
} else if (cost[data[j]] < cost[data[i]]) {

int temp = index[data[j]];
index[data[j]] = index[data[i]];
index[data[i]] = temp;

temp = data[j];
data[j] = data[i];
data[i] = temp;

i = j;
} else
break;
}
}

public int pop() {
int res = data[0];
data[0] = data[size - 1];
index[data[0]] = 0;
size--;
shiftDown(0);
return res;
}

public void push(int x, int c) {
if (index[x] == -1) {
cost[x] = c;
data[size] = x;
index[x] = size;
size++;
shiftUp(index[x]);
} else {
if (c < cost[x]) {
cost[x] = c;
shiftUp(index[x]);
shiftDown(index[x]);
}
}
}
}

As far as the code is concern, it is working fine for small s. How can i optimize this code for large value of nodes?

-

The only memory that you are allocating is the four arrays: data, index, cost, and eval. That means that if you are running out of memory then you probably need to allocate more memory. An array of primitives is just about as compact a structure as you're going to get.

You don't say what you mean by "large value of nodes", but you can figure that you will be allocating approximately 13 bytes (less because the boolean array will be packed) times the value of s passed into the constructor. I think the default heap is 64 MB, and some of that is allocated to other things, but you should be able to allocate at something in the millions range.

I added this main to your code and it showed that an array of 100,000 entries used just over 1.2 MB.

public static void main(String[] args) {
Runtime r = Runtime.getRuntime();

long t = r.totalMemory();
long f = r.freeMemory();
System.out.println("[Heap.main] " + t + "," + f);

Heap h = new Heap(100000);
h.init(0);
h.push(1,2);
System.out.println("[Heap.main] isEmpty returns: " + h.isEmpty());

t = r.totalMemory();
f = r.freeMemory();
System.out.println("[Heap.main] " + t + "," + f);
}
-
Thank you. Can you please suggest me some ways? My aim is to speed up Dijkstra's Algorithm. That is why i am using Min Heap as it is suggested by StackOverflow also. How can I get more speed up with higher number of nodes? –  Ravi Joshi Apr 19 '12 at 16:29
The amount of memory that the program is allowed to use is specified by Java runtime parameters (-Xmx specifically - see the documentation for the Java runtime you are using, such as docs.oracle.com/javase/1.5.0/docs/tooldocs/solaris/java.html) –  Donald.McLean Apr 19 '12 at 16:34
Ya.. I know about it. java -Xmx1024M will work. but is there any possible way to optimize this code? I can ignore boolean array eval for the time being. But what can be done with int array data index and cost? If anyhow i can change play with their size or is there any other optimized min heap code in java? Would be very helpful to me. –  Ravi Joshi Apr 19 '12 at 17:55
1. You can have a look at different dijkstra implementations how they did it and compare yours e.g. my own ;) karussell.github.com/GraphHopper 2. a minor change could be to use BitSet instead of boolean array (saves a bit memory but is probably slower) 3. you can use speed up technics (bidirectional dijkstra, contraction hierarchie, guided dijkstras like a star, using heuristics, ...) 4. instead of an own heap for 'smaller' datasets I've seen that the normal java heap (PriorityQueue) is sufficient and could be even faster –  Karussell Apr 20 '12 at 7:00
a minor btw: be sure that you understand that a star is NOT a heuristic. although it is often used as one –  Karussell Apr 20 '12 at 7:02