> How about a priority heap? It's much more useful to sort things by their min priority, but just telling me the priority at the end isn't helpful. You'll want the thing as well.

Sure, but again, at that point you're not taking the minimum thing, you're taking the thing with the minimum priority. And it wouldn't be strange to say that two things have the same priority (even if they're different things).