3
$\begingroup$

Question: There are several priority queue implementations listed on Wikipedia, along with amortized complexities of each of their basic operations:enter image description here Does anyone know of an implementation in which the known upper bounds for both the find-min and delete-min operations are $o(\log n)$?

Motivation: This paper describes an implementation of Dijkstra's algorithm that uses an abstract priority queue, as well as its computational complexity for various specific implementations of priority queues. I've tried to generalize their growth order computation as follows. If we let:

  • $\mathfrak m$ denote the growth order of the complexity of find-min
  • $\mathfrak r$ denote the growth order of the complexity of delete-min
  • $\mathfrak i$ denote the growth order of the complexity of insert
  • $\mathfrak d$ denote the growth order of the complexity of decrease-key
  • $\mathfrak e$ denote an asymptotic upper bound on the number of edges of a certain family of graphs as a function of the number of vertices
  • $\mathfrak n$ denotes linear growth order, i.e. $\mathcal O(n)$

then if I'm not mistaken, the growth order of the complexity of performing Dijkstra's algorithm on a graph from the specified family of graphs, as a function of the number of vertices of that graph, would be bounded above by the growth order $$\mathfrak n \cdot (\mathfrak m + \mathfrak r) + \mathfrak n\mathfrak i + \mathfrak e \cdot \mathfrak d$$ For Fibonacci trees, for instance, we would have $\mathfrak m, \mathfrak i, \mathfrak d$ all equal to constant growth order, and $\mathfrak r$ equal to logarithmic growth order $\mathfrak l$, in which case the above expression becomes $\mathfrak{n\cdot l} + \mathfrak{e}$, in agreement with $\mathcal O(n\log n + m)$, in agreement with the paper.

After computing this growth order for some of the other priority queue implementations, it seems like the most costly term for sparse graphs, in particular graphs in which the number of edges is $o(n\log n)$ in the number of vertices, is the contribution from the find-min and delete-min operations. Only if these operations are both (amortized) $o(n\log n)$ can we get the overall complexity of Dijkstra below $o(n\log n)$ for this family of graphs - hence my curiosity about whether there is an implementation of priority queues in which both complexities have a known upper bound that is $o(n\log n)$.

$\endgroup$
2
  • 2
    $\begingroup$ What are your requirements on the running time of insert? It is trivial to achieve the desired time bounds if you allow each insert to take $O(n)$ time. $\endgroup$
    – D.W.
    May 21, 2023 at 21:23
  • $\begingroup$ @D.W. Good point. Ideally, we would have all of find-min, delete-min, insert and decrease-key with known upper bounds that are all $o(\log n)$. Intuitively, it feels like there should be a way to take something like, say, a fibonacci heap and "sacrifice a little bit of efficiency" from the operations other than delete-min in order to bring delete-min just barely under $\mathcal O(\log n)$. $\endgroup$ May 22, 2023 at 1:45

1 Answer 1

6
$\begingroup$

It is trivial to build a heap where insert takes $O(n)$ time and find-min and delete-min take $O(1)$ time: simply store all the numbers in a linked list in sorted order.

It is not possible to build a heap where insert and delete-min both take $o(\log n)$ time, using only comparison operators, as this would imply a $o(n \log n)$-time comparison-based sorting algorithm, which is known to be impossible.

$\endgroup$

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.