- Elements are stored in a single dynamic data-structure $D$
- Element ranks are computed by: $\forall i \in n\quad f(i,\ x_i+1) : x_i \in \mathbb{Z^+}$
- The function $f$ is weighting based on the value of $i$
- $f$ can be redefined, when it is $D$ is restructured accordingly
Where $D$ supports insert in no more than $\mathcal{O}(\log_2 n)$, and delete-min, get-min, decrease-key in $\mathcal{O}(1)$. Linear space is preferred.
To use Haskell notation: (\(f,x) -> f x + 1)((\i -> i*2), 5)
. However I might change the weighting to e.g.: f = \i -> quot i 2
. Trivially one can construct new priority-queues for new definitions of f
. I would like it to restructure in less than $\mathcal{O}(n)$. Is that possible?
Is there a solution for the implementation of $D$ which takes less than $\mathcal{O}(n)$ to complete 4.?