Problem Detail: 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?
Asked By : Joe
Answered By : jbapple
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; }
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/880
