<p>It is trivial to build a heap where insert takes <span class="math-container">$O(n)$</span> time and find-min and delete-min take <span class="math-container">$O(1)$</span> time: simply store all the numbers in a linked list in sorted order.</p>
<p>It is not possible to build a heap where insert and delete-min both take <span class="math-container">$o(\log n)$</span> time, using only comparison operators, as this would imply a <span class="math-container">$o(n \log n)$</span>-time comparison-based sorting algorithm, which is known to be impossible.</p>

CC BY-SA 4.0
2023-05-22T01:58:49.237Z
2023-05-22T01:58:49.237Z
D.W.
<p><strong>Question:</strong> There are several priority queue implementations listed on Wikipedia, along with amortized complexities of each of their basic operations:<a href="https://i.sstatic.net/p1QO5.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/p1QO5.png" alt="enter image description here" /></a> Does anyone know of an implementation in which the known upper bounds for both the <code>find-min</code> and <code>delete-min</code> operations are <span class="math-container">$o(\log n)$</span>?</p>
<p><strong>Motivation:</strong> <a href="https://arxiv.org/pdf/2303.10034.pdf" rel="nofollow noreferrer">This paper</a> 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:</p>
<ul>
<li><span class="math-container">$\mathfrak m$</span> denote the growth order of the complexity of <code>find-min</code></li>
<li><span class="math-container">$\mathfrak r$</span> denote the growth order of the complexity of <code>delete-min</code></li>
<li><span class="math-container">$\mathfrak i$</span> denote the growth order of the complexity of <code>insert</code></li>
<li><span class="math-container">$\mathfrak d$</span> denote the growth order of the complexity of <code>decrease-key</code></li>
<li><span class="math-container">$\mathfrak e$</span> denote an asymptotic upper bound on the number of edges of a certain family of graphs as a function of the number of vertices</li>
<li><span class="math-container">$\mathfrak n$</span> denotes linear growth order, i.e. <span class="math-container">$\mathcal O(n)$</span></li>
</ul>
<p>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 <span class="math-container">$$\mathfrak n \cdot (\mathfrak m + \mathfrak r) + \mathfrak n\mathfrak i + \mathfrak e \cdot \mathfrak d$$</span> For Fibonacci trees, for instance, we would have <span class="math-container">$\mathfrak m, \mathfrak i, \mathfrak d$</span> all equal to constant growth order, and <span class="math-container">$\mathfrak r$</span> equal to logarithmic growth order <span class="math-container">$\mathfrak l$</span>, in which case the above expression becomes <span class="math-container">$\mathfrak{n\cdot l} + \mathfrak{e}$</span>, in agreement with <span class="math-container">$\mathcal O(n\log n + m)$</span>, in agreement with the paper.</p>
<p>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 <span class="math-container">$o(n\log n)$</span> in the number of vertices, is the contribution from the <code>find-min</code> and <code>delete-min</code> operations. Only if these operations are <em>both</em> (amortized) <span class="math-container">$o(n\log n)$</span> can we get the overall complexity of Dijkstra below <span class="math-container">$o(n\log n)$</span> 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 <span class="math-container">$o(n\log n)$</span>.</p>

CC BY-SA 4.0
2023-05-21T21:23:17.500Z
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.
D.W.
CC BY-SA 4.0
2023-05-22T01:45:50.410Z
@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)$.
Franklin Pezzuti Dyer
<cc.complexity-theory><graph-algorithms><ds.data-structures><asymptotics>
Priority queue implementation with both find-min and delete-min $o(\log n)$
Franklin Pezzuti Dyer
# Priority queue implementation with both find-min and delete-min $o(\log n)$

(Asked by: username_0 on 2023-05-21)

**Question:** There are several priority queue implementations listed on Wikipedia, along with amortized complexities of each of their basic operations:[![enter image description here](https://i.sstatic.net/p1QO5.png)](https://i.sstatic.net/p1QO5.png) 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](https://arxiv.org/pdf/2303.10034.pdf) 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)$.

**Tags:** cc.complexity-theory, graph-algorithms, ds.data-structures, asymptotics
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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)$.  

---

## 1 answers

### Answer by username_1 on 2023-05-22. Score: 6

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.


---

