From a textbook on computational problems, there's a question I've been pondering...
Q: If a priority queue has operations to add a value and show/remove the smallest value, show that for an implementation, which only accesses data by copying and comparing it, that the worst case complexity of an operation is $\Omega$(log n).
I have some questions about this. Firstly, I'm a little unsure as to the importance of the "accesses but does not mutate" bit of information. In what way would this affect the complexity? There is a hint that suggests that a result from a previous page that sorting under the same restrictions requires $\Omega$ (log n), which uses some logarithmic integration/simplification but I'm not sure how to take that result and make use of it here.
So far I'm stuck on a solution. Clearly the removal operation must have some way to compare the functions, but surely that means it should be bounded by $\Omega$ (n) since a naive solution would involve running each element of the queue to find the smallest?