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

algorithm data-structures priority-queue minimum-spanning-tree prims-algorithm
Geek picture Geek · Sep 27, 2012 · Viewed 9.3k times · Source

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

Shahbaz picture Shahbaz · Sep 27, 2012

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.

Related questions

Why does Dijkstra's algorithm use decrease-key?

Dijkstra's algorithm was taught to me was as follows while pqueue is not empty: distance, node = pqueue.delete_min() if node has been visited: continue else: mark node as visited if node == target: break for each neighbor of node: pqueue.…

Read More
What is the difference between binary heaps and binomial heaps?

I need to know the main difference between binary and binomial heaps regardless of the their structure difference that binary heaps can have only two child (tree representation) and binomial heaps can have any number of children. I am actually …

Read More
Change priority of items in a priority queue

Using Scala 2.9 to implement a kind of Dijkstra algorithm (pseudo code) val queue = new PriorityQueue queue.insert(...) while (!queue.isEmpty) { val u = queue.extractMin queue.foreach { v => if (condition(u, v)) queue.decreaseKey(v, newPriority) } } I'd like to change …

Read More