Heap is the one to choose. Priority queue always pops out the highest valued element(the highest value is defined using weak ordering criterion), pop_heap will make sure the second highest element is placed on top after the first one is popped out, push_heap will also make sure the highest value is placed on top of the queue. In many cases, this is all you want - the highest valued element, which is what priority queue is operating on..

I would use a linkedlist here. I will maintain the linkedlist in a descending order/ The add() method will intake a node and it loops from root and postions in appropiate position O(n) Peek or poll returns the root element.

I got this question as well. However, the answer is impossible in constant time. A self balancing tree is one way to implement this. In that scenario you have O(log n) time for insertion and removal. You can always have the get minimun in constant time. A van Emde Boas tree or Fusion Tree can speed up this time, but not bring it to constant time.

I had said red black tree. He seemed to agree

Would a heap not be more appropriate?

Did you get the job?