0
$\begingroup$
  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.?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – D.W. ♦
    Dec 26, 2014 at 19:42
  • $\begingroup$ For a binary heap, makeheap runs in $O(n)$ time. What priority queue data structure were you planning to use? $\endgroup$
    – D.W. ♦
    Dec 27, 2014 at 3:22

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.