使用優先級隊列實現Dijkstra算法

我正在使用優先級隊列實現Dijkstra算法，我想要一個函數來從堆中移除一個元素，但我只能從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(); 
} 
}

來源

2014-01-21 user3218548

使用簡單的索引陣列Positions[Vertex]跟蹤頂點的在堆和記錄(Vertex,Distance)如堆數組元素。但僅僅實現這是不夠的，因爲在任何例程中，當你在堆上進行交換操作時，需要更新頂點的位置。

來源

2014-01-21 14:09:18

使用優先級隊列實現Dijkstra算法

回答

相關問題