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

  • 1
    $\begingroup$ It seems you are refering to a specific implementation of priority queue. Can you provide a source? $\endgroup$ – md5 Jun 21 '17 at 15:21
  • $\begingroup$ @md5 CLRS? e.g. web.cse.ohio-state.edu/~lai.1/2331/4.heapsort.pdf | Chapter 5: Priority Queues $\endgroup$ – denis631 Jun 21 '17 at 15:38

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.

  • $\begingroup$ Yes, but after every extract max I need to update the log(n) entries in the HashTable, right? But your approach definitely makes sense. Thanks $\endgroup$ – denis631 Jun 21 '17 at 15:43
  • 1
    $\begingroup$ @denis631, yup. Sometimes you won't need a hash table; you can have a slot in the object that holds the index (it's basically a back-pointer into the priority queue). Yes, you'll need to update it each time it is moved. $\endgroup$ – D.W. Jun 21 '17 at 16:23

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.

  • $\begingroup$ Updating the heap requires only $O(\log n)$ updates to the hash table, not $O(n \log n)$. It's one update to the hash table per item updated in the priority queue. Thus this increases the cost by a constant factor, and doesn't change the asymptotic complexity. (Treating hash table operations as $O(1)$, which is approximately right in practice.) $\endgroup$ – D.W. Jun 21 '17 at 17:16
  • $\begingroup$ Yes. ... an additional O(nlogn) hit ... Which is a constant factor of 2. Still This works only when you change priority more than log(n) times . Below that, linear is more economic. $\endgroup$ – inquisitive Jun 21 '17 at 17:34
  • $\begingroup$ @inquisitive very interesting read. But I didn't get where did O(N logn) come from. I mean O(logn) for logN update in the hash map for increase key operation. So O(logn) is definitely cheaper than linear time. We have to pay the O(n) memory price though. $\endgroup$ – denis631 Jun 21 '17 at 21:55
  • 1
    $\begingroup$ @denis631, edited answer with more details. $nlogn$ comes from $n$ times performing extract_min. Each extraction causes shift in $logn$ elements - causes hash table access for $logn$ elements. The linear time is occasional but $logn$ is everytime. $\endgroup$ – inquisitive Jun 22 '17 at 3:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.