Please explain the relation between Decrease-Key and Extract-Min operations in priority queues

Question

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.

Answer 1

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.