Why do we need increase_key procedure in max priority queue?

Question

Since if I want to increase the priority of a specific node, how do I find the node without linear searching it.

I need to pass the index to this function, which is in a way a bottleneck. So the question is, how can I avoid it? Or exactly this data structure doesn't provide any solution for this problem?

Link: web.cse.ohio-state.edu/~lai.1/2331/4.heapsort.pdf | Chapter 5: Priority Queues

Answer 1

In some algorithms, you'll be able to remember the index.

In others, you might need a separate data structure (e.g., a hash table) that maps from the node to its index. When you insert a node into the priority queue, you also add it to that mapping. When you need to know a node's index (e.g.,to call increase_key), you look it up in that mapping.

Answer 2

In general CLRS case, yes, you need to search the array to find the element whose key (priority) has to be changed. Searching in binary heap is a $O(n)$ operation so it is a linear search.

What CLRS does not mention is that even with a linear search you cannot necessarily locate your candidate. In an integer array, the only information the elements have is their key - their priority. The array elements do not know their domain identifier - (say) EMPLOYEE_ID or PROCESS_ID. If all the elements have unique priority key then the search is fruitful, otherwise with multiple items with equal priority the linear search fails. The solution is to either have an array of structs or a 2D array with one column for priority code, another for its domain identifier.

Point is - what is in CLRS is a bare minimum implementation. You got to augment the system anyway.

Take an example of cpu process scheduling using priority queue. Each process has a PID and Priority. Lets say we have a ready queue of $n$ processes. We iteratively pick the process with highest priority, remove from queue and process it - rinse and repeat. Each iteration takes $O(1+ log(n))$ time. How rare is when a processes priority is changed? Assuming very rare - in cpu terms, we may take an occasional hit of linear search among a thousand elements.

But if the priority change is very frequent - in cpu terms, or the linear search space is very large then we do have to augment the system with some additional data structure. Now D.W.'s answer comes to play. You have to maintain a mapping between the PID of the process and its index in the array. With this approach, as you correctly point out, you need to keep the hash table in sync with the heap. To do this consider these two implications:

1. You need to tag each entry in the heap with PID anyway - ie. use an array of structs or a 2D array or something like that.

2. Whenever you "use" your queue by extracting the top item, the heap reorganizes itself by shifting roughly $log(n)$ items within the array. That is why cost of extraction is $O(logn)$. Now note that for each of these elements moved in the array, you got to update the item's tag in the hash table too. So for one extraction, the cost doubles. You got to move $log(n)$ items and update the hash table for each of them.

In extracting all $n$ items, we are now taking an additional $n$ times $log(n)$ hit in updating the hash table. This entire $nlogn$ expense will remain unused until someone needs to perform a search. What if during the entire lifespan of the activity, (say) we performed $k$ searches against $k$ calls to increase_key. Without the augmentation we would have to pay $O(nk)$ for $k$ linear searches over $n$ elements. Question is do we pay an upfront price of $nlogn$ or pay $nk$ as we go?

Evidently, in cases when $(nk < nlogn) => (k < logn)$, linear search is not that bad either. This is an engineering design decision.