implementing Dijkstra's Algorithm using priority queue

Question

I'm implementing Dijkstra's Algorithm using priority queue, I want a function to remove an element from the heap but I can only send it the vertex index from the Dijkstra's main and I can't find its position on the heap and I can't afford to do a binary search. Any ideas?

public class MinHeap {
Vertex[] Heap = null; // Vertex array
int Lenght;
int Size;
int[] elementsPostion; // Array of Index of Vertices

private int parent(int i) {
    if (i % 2 == 0)
        return (i / 2) - 1;
    else
        return i / 2;
}

private int leftChild(int i) {
    return (2 * i) + 1;
}

private int rightChild(int i) {
    return (2 * i) + 2;
}

// Initialize PQ
public MinHeap(int len) {
    Lenght = len;
    Size = 0;
    Heap = new Vertex[Lenght];
    elementsPostion = new int[Lenght];
}

// Extract Min
public Vertex ExtractMin() {

    Vertex v;
    v = Heap[0]; // min = index of min
    elementsPostion[Heap[0].index] = -1;
    Heap[0] = Heap[Size - 1];
    elementsPostion[Heap[0].index] = 0;
    Size = Size - 1;
    minHeapify(0);
    return v;
}

// ----------------------------
// Sort Inside PQ
public void minHeapify(int pos) {
    int L;
    int R;
    L = leftChild(pos);
    R = rightChild(pos);
    while (pos < Size
            && (Heap[L].minDistance < Heap[pos].minDistance || Heap[R].minDistance < Heap[pos].minDistance)) {
        Vertex tmp;
        if (Heap[L].minDistance < Heap[R].minDistance) {
            elementsPostion[Heap[L].index] = pos;
            elementsPostion[Heap[pos].index] = L;

            tmp = Heap[L];
            Heap[L] = Heap[pos];
            Heap[pos] = tmp;
            pos = L;
        } else {
            elementsPostion[Heap[R].index] = pos;
            elementsPostion[Heap[pos].index] = R;

            tmp = Heap[R];
            Heap[R] = Heap[pos];
            Heap[pos] = tmp;
            pos = R;
        }
        L = leftChild(pos);
        R = rightChild(pos);
        /*
         * if(pos< Size && Heap[L].minDistance <Heap[pos].minDistance)
         * min=L.index; else min=pos; if(R.index<=Size &&Heap[R]<Heap[pos])
         * min=R.index; if(min !=pos) { int tmp = Heap[pos]; Heap[pos] =
         * Heap[min]; Heap[min] = tmp; minHeapify(min); }
         */
    }

    // swap in P.Q with Swapping in arrayofVertNum
}


// insert vertex
public void insertVertex(Vertex element) {
    Heap[Size] = element; // size = number of verticies
    HeapDecreaseKey(Size, element); //
    Size++;
}

// Compare when insert with Parents
public void HeapDecreaseKey(int index, Vertex key) // bta5od el element ele hy3mlo insert ,,
{ 
    // index=size , key=element // add in last
    // Heap[index]=key; //add in last
    Vertex v = new Vertex(key.index, key.xPos, key.yPos, key.minDistance);

    //int swap;
    boolean b = false;
    while (index > 0
            && Heap[parent(index)].minDistance > Heap[index].minDistance) {
        b = true;
        elementsPostion[Heap[parent(index)].index] = index;
        elementsPostion[Heap[index].index] = parent(index);

        Vertex tmp = Heap[parent(index)];
        Heap[parent(index)] = Heap[index];
        Heap[index] = tmp;

        index = parent(index);
    }
    if (b == false)
        elementsPostion[key.index] = index;

    // Swap in array
}

// check if PQ is empty
public boolean isEmpty() {
    return Heap == null;
}

public void display() {



    for (int i = 0; i < Size; i++) {
        System.out.print(Heap[i].minDistance);
    }
    System.out.println();
}
}

Vikram Bhat Vikram Bhat · Accepted Answer · 2014-01-21T14:09:18

Keep track of the vertex in the heap using simple index array Positions[Vertex] and record (Vertex,Distance) as element in heap array. But implementing only this is not enough because you need to update positions of vertex very time you do swap operation on heap in any routine.

implementing Dijkstra's Algorithm using priority queue

1 Answers