Priority Queue with a find function - Fastest Implementation

Question

I am looking at implementing a priority queue with an added requirement, a find/search function which will tell whether an item is anywhere within the queue. So the functions will be: insert, del-min and find.

I am unsure whether I should use a Heap or a Self-balancing binary search tree. It appears PQs are usually implemented with a Heap, but I am wondering if there is any advantage in using a binary search tree since I also need that find function.

Furthermore, on average I'll be doing more inserts than deletes. I am also considering a d-ary heap. Basically, every second counts.

Thanks!

Answer 1

Why can't you just use a Priority Queue and a Set? When you enqueue something, you add it to the set. When you dequeue it, you remove it from the set. That way the set will tell you if something is in the queue.