Looks like the $\Omega(\dfrac{\log n}{\log\log n})$ barrier has been overcome by modifying the analysis from the chronogram technique. The new [lower] $\Omega(\log n)$ bound has been proved for ...

Hash table lookup can always be $O(1)$ for static sets, see the 2002 paper by Arne Andersson and Mikkel Thorup: Dynamic ordered sets with exponential search trees Firstly, we give the ﬁrst ...

An option would be to use the Signature Scheme of , size-based filtering: a scheme which uses size information to reduce the number of set pairs that need to be considered. They also experiment ...

Okay, finally got you the complexity you were looking for, and what's best, I found it in the literature: Worst-Case Complexity Delete: $\bf\mathcal{O}(1)$ Delete-min: $\bf\mathcal{O}(1)$ Find-min:...

Worst-case complexity Insert: $\mathcal{O}(1)$ Find-min: $\mathcal{O}(1)$ Decrease-key: $\mathcal{O}(1)$ Delete: $\mathcal{O}(\log \log n)$ Space: $\mathcal{O}(n)$ Proof THEOREM 1. We can implement a ...

Approaching this problem by maintaining two data-structures: an Array and a Binary Tree. To maintain indexing in the array, previously you'd have the $\Omega(\dfrac{\log n}{\log\log n})$ bound; but ...

As a simple proof-by-contradiction take a look at any algorithm who's complexity depends on more than one variable, e.g.: $\mathcal{O}(nk)$. In such a case it is rarely possible to express running ...

How about using a Strict Fibonacci Heap? - Here are the worst-case complexities: $$\mathcal{O}(1) \text{ find-min}$$ $$\mathcal{O}(\log_2 n) \text{ delete-min}$$ $$\mathcal{O}(1) \text{ insert}$$ ...

Worst-case complexity $\mathcal{O}(log\ M)$ insert, search, delete [see 'Lemma 3.1'] $\dagger\ \mathcal{O}(1)$ findMin, findMax, extractMin, extractMax, predecessor, successor $2M + \mathcal{O}(log\ M)... View answer 0 votes Finally a simplification of the Brodal queue has been released, which unlike; are worst-case values (rather than amortised). Insert:$\mathcal{O}(1)$Find-min:$\mathcal{O}(1)$Decrease:$\...

Worst-case complexity $\boldsymbol{\mathcal{O}(1)}$ insertion $\boldsymbol{\mathcal{O}(log\ \textbf{min}\{w_x, q_x\})}$ get-min, extract-min, delete, and decrease of an element $\boldsymbol{x}$ Where ...

Analysis Insert: $\mathcal{o}(n\ log\ log\ n)$ Search: $\mathcal{o}(log\ log\ n)$ Delete: $\mathcal{O}(1)$ Space: $\mathcal{O}(n)$ Get-Min: $\mathcal{O}(1)$ Extract-Min: $\mathcal{O}(1)$ ...

Find-min in $O(1)$ with expected update time of $O(\sqrt{log\text{ }log\text{ }n})$ See the 2007 paper: Equivalence between priority queues and sorting by Mikkel Thorup. Note: He refers to the 2002 ...
Worst-case complexity Insert: $\mathcal{O}(1)$ Find-min: $\mathcal{O}(1)$ Decrease-key: $\mathcal{O}(1)$ Delete: $\mathcal{O}(\log \log n)$ Space: $\mathcal{O}(n)$ Proof THEOREM 1. We can implement a ...