Min Heap implementation with Dijkstra's algorithm

Question

I am implementing Dijkstra's Algorithm using Min Heap to speed up the code.

For a small number of nodes, the code is really running very fast. But for a 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 concerned, it is working fine for small s. How can I optimize this code for a large value of nodes?

• user3742120: I was able to solve this question TSHPATH in spoj with your code... I think maybe you are not taking the Graph as a adjacency list... I am attaching the link to the code here: ideone.com/951QAJ

Answer 1

I'm with @DonaldMcLean, in that I don't see a possibility of memory leak here. So if you run out of memory that must be because given the size of the heap you want to create, you didn't give enough memory to the JVM to contain all your arrays.

There's something to save you some memory though: the eval array is completely unused, it's just taking up memory for no reason, so delete that.

---

In terms of code review, there are a couple of things that you should definitely improve:

• Don't assign to static variables from instance methods
• The data, index, cost shouldn't be static, but should be private members of the Heap class.
• A more efficient way to fill the index array with -1 values is Arrays.fill(index, -1)
• You don't need to fill a boolean array with false values, boolean arrays are like that by default
• You do a lot of swapping of elements in the index and data arrays. Instead of spelling out every time the temp = ...[i]; ...[i] = ...[j]; ...[j] = temp idiom, it would be better to create a helper swap method and shorten and simplify the code

Answer 2

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);
}

• ravi: 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?
• Donald.McLean: 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)
• ravi: 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.
• Karussell: 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: a minor btw: be sure that you understand that a star is NOT a heuristic. although it is often used as one