Q:

Why does decreasekey in Dijkstra's algorithm take O(logN) time?

for the updating part,
for all neighbors w of u:
    if dist[w] > dist[u] + l(u,w)
        dist[w] = dist[u] + l(u,w)
        prev[w] = u
        decreasekey(H,w)

Here, w is the ID of the node, I think it should be like pair(ID,key) which key is the dist[ID]. 
If so, finding the node with ID w on a priority queue should cost O(N) time rather than O(logN) time. 
Then, why is decreasekey in Dijkstra's algorithm takes O(logN) time?

A:

The heap implementation used for Dijktra is different from conventional priority queue implementation so inbuilt libraries of priority queue would not help you. The only solution is to implement your heap and keep track of position of each vertex in heap in an array. You need to update the pointers to vertex when u do insert or delete into heap. When u have to do decreaseKey in heap you have the direct location of vertex in heap and u can update the value of Key at that location . Use Heapify to reorder the heap (which takes O(logn)).

