Algorithm for Broken Priority Queue

Question

IF a priority queue has two operations: insert and broken_min. Where broken_min returns either the first or second minimum item.

These cannot both be implemented in o(logn) time. I think this is because insert uses broken_min and would then have to do more checks to see if it has the maximum or not.

Is this correct reasoning?

Answer 1

Yes, I believe you're correct.

A priority-queue is typically implemented as a heap:

A heap is a specialized [binary-]tree-based data structure ... the keys of parent nodes are less than or equal to those of the children and the lowest key is in the root node (min heap).

broken_min can be implemented in O(1) since one of the children will be the second largest element, so we can just check both.

But insert will take Ω(log n), which isn't o(log n) (but would indeed be O(log n)).

I doubt you'll find a priority-queue implementation that could satisfy the given running times, but saying it's impossible would be irresponsible.

Note: I assume you meant little-o (a strict upper bound, as opposed to big-O, which is a greater-or-equal upper bound) given the tag, although big-O is used most of them time, and little-o is almost never used (as far as I've seen).