Midterm #2 b)

[Hudon]

Would it be possible to get the solution for this question? (from our midterm)
"Prove that no realization of the Priority Queue ADT that only uses comparisons between keys can have running time O(1) for both the insert and delete-max operations."

I don't understand how it can be soundly proven that no data structure will ever be able to do this.

[Gareth Davies]

Post by Hudon
Would it be possible to get the solution for this question? (from our midterm)
"Prove that no realization of the Priority Queue ADT that only uses comparisons between keys can have running time O(1) for both the insert and delete-max operations."
I don't understand how it can be soundly proven that no data structure will ever be able to do this.

You can sort a list using a priority queue by inserting each list item
into the queue, and then calling delete-max repeatedly and storing the
returned items in a new list. If the list has length n and both PQ
operations have running time O(1), then the PQ sort has O(n) time, which
violates the Omega(nlogn) lower bound for comparison-based sorts.

[cs240]

That is correct.