My teacher gave me a pseudocode of Dijkstra's algorithm using binary heap including the following steps (x was just extracted from the heap):
For each vertex y such that it is a node for it in a heap and there is an edge (x,y) in a graph:
1) Dist[y] = min(Dist[y], Dist[x] + w(x,y))
2) Update y's node in the heap
It is also said that the complexity of these steps for the whole algorithm is O(ElogV).
But I can't undestand why the step "that it is a node for it in a heap" doesn't influence on complexity in the bad way. Because it means that we should find every neighbor of x in the heap, but there are no efficient ways of searching for node in the heap (only linear search comes to my mind), and it means that for each y we should:
1) Find it in the heap - which takes O(number of nodes in the heap) watches
2) Update it - which takes O(logV) time
This way, it will take O(V*E*logV+(V-1)*E*logV+...) = O($V^2$*E*logV), since the number of nodes in the heap decreases on each step by 1. Am I losing something?