0
$\begingroup$

I recently got into a discussion about Priority Queues when the requirements allow for "best effort" removal (i.e. the removed key may not always be THE very highest priority, but it is relatively close).

After thinking about it a bit I stated "I could probably make it $O(1)$ by using buckets" and approximating the minimum (to bucket size precision). I was politely told that I was wrong. Not taking no for an answer, I later went to Google and found the ample literature on the subject, which seemed to confirm I was wrong :-|

Note that the closely related question, Unique integer priority queue with both $O(1)$ insert and extract-min?, does not allow for approximation, so the answers don't apply to my question.

I was told the standard solution to this problem is to use a queue where keys are appended to the end in $O(1)$ and read from the head in $O(1)$ and which is then periodically sorted in $O(\log N)$ or whatever sorting algorithm you can find.

Assuming 64-bit integers as keys, and a precision of $ \pm 127$ (a 56-bit bucket)... Can't you just hold the buckets in a sparse array (so as not to require $2^{56}$ words of memory)... problem solved?

$\endgroup$
6
  • 1
    $\begingroup$ What do you mean by a "sparse array"? How do you plan to implement that? With a binary search tree or somesuch? Then it's not $O(1)$; it is $O(\log n)$. $\endgroup$
    – D.W.
    Sep 30, 2017 at 1:25
  • $\begingroup$ The sparse array itself would be hash or bucket-based, to provide O(1) access. $\endgroup$
    – Alex R
    Sep 30, 2017 at 5:46
  • $\begingroup$ "Note that the closely related question, Unique integer priority queue with both O(1) insert and extract-min?, does not allow for approximation, so the answers don't apply to my question." -- if a method solves the problem exactly, it also solves them approximately. $\endgroup$
    – Raphael
    Sep 30, 2017 at 5:50
  • $\begingroup$ Hash tables do not provide worst-case O(1) access. $\endgroup$
    – Raphael
    Sep 30, 2017 at 5:51
  • $\begingroup$ It is averaged/amortized for hash is O(1). The exact solution is not O(1). $\endgroup$
    – Alex R
    Sep 30, 2017 at 7:23

1 Answer 1

1
$\begingroup$

Your proposed data structure is simply a hash table with some rounding to reduce the number of buckets. Effectively, all this does is divide the problem complexity by some constant factor (128 in your example).

You have no hierarchy in your design, so there is no way to have O(1) access to the smallest/largest non-empty bucket. To achieve this feature efficiently, you're already pretty much bound to some type of priority queue. This class of data structures is well studied, and has various implementations with typically very low bounds on complexity.

$\endgroup$

Your Answer

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

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