Priority queue implementation with both find-min and delete-min $o(\log n)$

Question

Question: There are several priority queue implementations listed on Wikipedia, along with amortized complexities of each of their basic operations: 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)$.

Answer 1

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.