12
$\begingroup$

A Fibonnaci Heap supports the following operations:

  • insert(key, data) : adds a new element to the data structure
  • find-min() : returns a pointer to the element with minimum key
  • delete-min() : removes the element with minimum key
  • delete(node) : deletes the element pointed to by node
  • decrease-key(node) : decreases the key of the element pointed to by node

All non-delete operations are $O(1)$ (amortized) time, and the delete operations are $O(\log n)$ amortized time.

Are there any implementations of a priority queue which also supportincrease-key(node) in $O(1)$ (amortized) time?

$\endgroup$
1
  • $\begingroup$ @Raphael if you increase the key of the minimum element so that it is now the largest key, it's not immediately obvious (at least to me) that you don't have to do a super-constant amount of rebalancing. $\endgroup$
    – Joe
    Commented Mar 29, 2012 at 22:35

1 Answer 1

10
$\begingroup$

Assume you have a priority queue that has $O(1)$ find-min, increase-key, and insert. Then the following is a sorting algorithm that takes $O(n)$ time:

vector<T>
fast_sort(const vector<T> & in) {
  vector<T> ans;
  pq<T> out;
  for (auto x : in) {
    out.insert(x);
  }
  for(auto x : in) {
    ans.push_back(*out.find_min());
    out.increase_key(out.find_min(), infinity);
  }
  return ans;
}
$\endgroup$
4
  • 1
    $\begingroup$ I had assumed that (de|in)crease-key only did plus or minus one. $\endgroup$
    – Raphael
    Commented Mar 30, 2012 at 7:13
  • $\begingroup$ And does there exist a DS that allows increase-key operation in constant time but decrease in logarithmic (or more)? (For a min-heap) $\endgroup$ Commented Jul 2, 2018 at 0:23
  • 2
    $\begingroup$ @GonzaloSolera: The impossibility proof in this answer doesn't care about decrease-key; O(1) find-min, increase-key, and insert are already a problem together (and the proof's dependence on insert isn't really necessary; O(n) heapify is enough, or we can probably reuse the same heap over multiple sorts to prove it violates comparison sort bounds regardless of the cost of heapify or insert). $\endgroup$ Commented Jul 2, 2018 at 17:23
  • $\begingroup$ Okay sorry, I missed read that. Thanks for your comment! $\endgroup$ Commented Jul 3, 2018 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.