Приоритетная очередь STL с делает дубликаты ключа - действительно ли это возможно?

Приоритетная очередь STL позволяют, делают дубликаты ключа??

Да.

Если это делает то, что должно я рассматривать

То, что порядок между равными элементами может измениться произвольно.

и какой предикат я должен использовать?

Это Вы имеете в виду? Это зависит полностью от Вашей семантики.

У Konrad есть большой ответ, для добавления к этому. Необходимо знать, что priority_queue не обязательно имеет высокую эффективность. Согласно этой странице http://www.cs.brown.edu/~jwicks/libstdc++/html_user/classstd_1_1priority__queue.html, похоже, что это реализовано путем выполнения make_heap, pop_heap, и т.д. на всех операциях для получения самого высокого приоритета.

re-heapifying, может быть дорогим по сравнению с другими структурами данных, в зависимости от Вашего варианта использования.

Да, это поддерживает, делают дубликаты ключа.

От doucumentation:

void push(const value_type& x) Inserts x into the priority_queue.
                               Postcondition: size() will be incremented by 1. 

Простой тест подтверждает это:

int main() {
  priority_queue<int> q;
  q.push(5);
  q.push(5);
  cout << q.top() << endl;
  q.pop();
  cout << q.top() << endl;
  q.pop();
}

Выводы:

5
5

Что касается предиката, используйте то, что Вы использовали бы, прежде - ничто гарантируемое приоритетной очередью не повреждается путем разрешения равных элементов, таким образом, алгоритм должен работать просто великолепно.