CareerCup

Can't we just use hashmap and hashset for this, it will be O(1) where BST will take O(logn)

No. In a BST you have a total ordering (think printing in-order). That is not necessary for a priority queue. A priority queue is typically implemented as a heap.

@Anonynous1: So Heap does not require a total order? Priority Queue does not require a total order? What are you talking about?

In a BST you can determine if an element is present or not in O(Log(n)) time. You can't do that in a heap. If an element is smaller than the maximal element in the heap (the root), you don't know if that element is in the left branch or the right branch. In a priority queue you of course don't care about anything but the element of highest priority. Hence no reason for a total ordering.

Data in a BST is completely sorted. That is not the case with a priority queue. Building a BST is O(n log n). In contrast, a priority queue using a heap can be built in O(n). Hence using a BST for a priority queue is wasteful.

LOL@ Anonymous. First search for what "Total order" even means (as pointed about by eugene).

And, priority queue can be implemented in terms of binary search trees. That is all Varun is saying.

Your objections are nonsense.

a trie is not a BST