Simple answer is don't clear it!
priority_queues are designed to have stuff inserted in and sorted in priority order. They not designed to have stuff removed from them, well, except by yanking stuff off the front. If you want to clear it then bin the object and start again:
q = std::priority_queue<int>();</int>
Failing that you could always just repeatedly pop stuff off the queue unitl it's empty:
while( !q.empty() ) q.pop();
For me the first way is a lot cleaner but YMMV.
Cheers,
Ash
PS: I wouldn't worry about the costs of the second method. There's no reason why you can't implement pop to take hardly any time at all, just enough to destruct the element.