0
$\begingroup$

QUESTION: Can we Implementing priority queue with hash table please?

As I understand, dictionary/hash table does not have sorting mechanism inside. It adds pairs of $<key,value>$ to hash table. So the keys in PQ would correspond to keys in hash table, however, keys are added such that elements are assigned a priority (min/high), which is not part of hash table implementation. So, what would you suggest please here?

Improve this question
$\endgroup$
1
  • $\begingroup$ Hash tables are by design not sorted. The most basic implementation of a priority queue that i know of uses a heap instead - and keeps both the key and the value in each node (but of course uses only the priority key to sort) $\endgroup$
    – nir shahar
    Commented Oct 18, 2021 at 6:19

1 Answer 1

Reset to default
1
$\begingroup$

You just build a priority queue (usually implemented as a heap) with items that are pointers to keys in your hash table. Connected to the hash table, and the hash table will modify the priority queue whenever keys are added or removed. This requires of course that keys support not only "equality" but also "ordering".

You might only build the priority queue when someone wants an iterator, because a priority queue doesn't allow you directly to iterate in sorted order; you have to destroy the priority queue to achieve that. A priority queue can only give you the first element in the queue, not all elements in sorted order.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you. If both have O(1) access time for get min/max and for search respectively. What advantage does this approach have you think please? $\endgroup$
    – Avv
    Commented Oct 18, 2021 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.