使用优先级队列实现Dijkstra算法

Question

我正在使用优先级队列实现Dijkstra的算法，我想要一个函数从堆中删除一个元素，但我只能从Dijkstra的主节点索引中向它发送顶点索引，我找不到它在堆上的位置，我负担不起进行二进制搜索。有什么想法吗？

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

Answer 1

使用简单索引数组< code>Positions[Vertex]跟踪堆中的顶点，并将< code >(顶点，距离)记录为堆数组中的元素。但是仅仅实现这一点是不够的，因为每次在任何例程中对堆进行交换操作时，都需要更新顶点的位置。