11
$\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$
  • $\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 Mar 29 '12 at 22:35
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$
  • 1
    $\begingroup$ I had assumed that (de|in)crease-key only did plus or minus one. $\endgroup$ – Raphael Mar 30 '12 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$ – Gonzalo Solera Jul 2 '18 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$ – user2357112 supports Monica Jul 2 '18 at 17:23
  • $\begingroup$ Okay sorry, I missed read that. Thanks for your comment! $\endgroup$ – Gonzalo Solera Jul 3 '18 at 9:22

Your Answer

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

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