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?

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