What is the relation between EXTRACT-MIN operation and DECREASE-KEY operations in priority queue? I encountered this in the lecture for minimum spanning problem using Prim's algorithm.
The professor from MIT refers to it at point 01:07:16 seconds in the video but I am not getting it. Can some one please clear this up for me?
P.S: I feel comfortable with my understanding of Priority Queues otherwise.
This sequence:
DECREASE-KEY(node, -infinity)
EXTRACT-MIN
Has a simple meaning:
DELETE-KEY(node)
What it basically does is to make sure a certain node gets to the top of the queue and then removes it.
In Prim's algorithm, DECREASE-KEY is used to update the weight of nodes not yet included in the tree. As a result, a node that was thought to be too far may now move closer to the top of the queue (and therefore would be EXTRACT-MINed sooner).
I can't view the video right now, but my guess is that what your professor meant is that DECREASE-KEY increases the chances of a node to be EXTRACT-MINed and is in fact used for the same reason, and hence a sort of relationship.