wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Priority Queue Operations
        
(Message started by: Barukh on Jul 6^th, 2014, 11:10am)

Title: Priority Queue Operations
Post by Barukh on Jul 6^th, 2014, 11:10am

Many literature sources on Priority Queues list the following set of operations: Insert, Minimum, Extract-Minimum, Decrease-Key, Delete (see, e.g. Cormen, Leiserson, Rivest book on Algorithms).

Note that Increase-Key is not included in this set. Why is this? Is it because the operation is rather unusual, or there is no more efficient implementation than just Delete/Change-Key/Insert?

Title: Re: Priority Queue Operations
Post by rloginunix on Jul 6^th, 2014, 12:10pm

1). I don't think that operation is unusual. It happens in real life all the time. My work load is a priority queue. When a previously lower priority item becomes "hot" all of a sudden my manager will tell me "stop doing what you are doing and do this instead". Apply this to many team members, teams, departments ...

2). In practice I deal with multi-thread-safe containers only. So I'd rather have that operation - you need to lock/unlock only once vs. twice for the Delete/Change/Insert. Not to mention the data consistency issues.