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.?

| cite | improve this question | |
$\endgroup$
  • $\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 '14 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 '14 at 3:22

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.