# Dynamically weighted priority queue?

1. Elements are stored in a single dynamic data-structure $D$
2. Element ranks are computed by: $\forall i \in n\quad f(i,\ x_i+1) : x_i \in \mathbb{Z^+}$
3. The function $f$ is weighting based on the value of $i$
4. $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.?

• The answer is going to depend a lot on how $f$ is represented / provided, and what class of functions $f$ are allowed. Is $f$ represented algebraically? Or is it represented as an arbitrary function in the language, where the data structure knows nothing of the structure of $f$ and only has the ability to evaluate it on inputs of its choice? If the latter, it seems clear we cannot possibly avoid evaluating $f$ $n$ times whenever it changes, so you can't possibly run faster than $O(n)$ time. Am I misunderstanding something? – D.W. Dec 26 '14 at 19:42
• For a binary heap, makeheap runs in $O(n)$ time. What priority queue data structure were you planning to use? – D.W. Dec 27 '14 at 3:22