www.cise.ufl.edu/~sahni/cop5536/powerpoint/lec10.ppt

Interesting that a data structure exists for this - I hadn't heard of that. It does make sense, in that a heap has a lot of "unstructured" space, but I would be hard pressed to derive that in an interview. My initial thought was to simply use a binary tree - min and max can be easily found by strictly moving left and right as far as possible, with log(n) performance. It's not exactly a priority queue (O(1) < O(log(n))) but it's pretty close until you get into ridiculous territory (a billion elements requires 30 left/right traversals).