Well, priority queue is rather an interface than a particular data structure.

When ppl say "priority queue" they typically mean "min-max heap". If your guess is the same then it is not the best guess. Min heap gives you O(log(N)) time for push/pop. And this problem has a O(1) (or very close to that) solution.