Min Heap implementation with Dijkstra's algorithm

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 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];
dat

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

StackExchange Code Review Q#11015, answer score: 3