You're hiring the candidate who happened to use one somewhat recently. The same candidate has completely forgotten other concepts and would have looked like a fool if questioned.
Requiring to implement a priority queue is harsh and no one should do this at the interviews.
Asking "what is a priority queue" is a totally fair question (if your job may reasonably require it), because knowledge that such things exist is a big part of being a senior person. You don't have to be able to know the class name, or exact notation, but you should be able to know what to Google for.
A person who does now know what a priority queue is will happily write O(n^2) algorithm which repeatedly calls max() and completely kill your app performance. There would be no opportunity to Google anything, because only senior people get business requirements, not names of algorithms they need to use.
Asking "what is a priority queue" is a totally fair question (if your job may reasonably require it), because knowledge that such things exist is a big part of being a senior person. You don't have to be able to know the class name, or exact notation, but you should be able to know what to Google for.
A person who does now know what a priority queue is will happily write O(n^2) algorithm which repeatedly calls max() and completely kill your app performance. There would be no opportunity to Google anything, because only senior people get business requirements, not names of algorithms they need to use.