Author |
Topic: Priority Queue Operations (Read 1255 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Priority Queue Operations
« on: Jul 6th, 2014, 11:10am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Priority Queue Operations
« Reply #1 on: Jul 6th, 2014, 12:10pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print