| Relaxed Heaps: An Alternative to Fibonacci Heaps, (1998) | |||||||||
Abstract | |||||||||
| The relaxed heap is a priority queue data structure that achieves the same amortized time bounds as the Fibonacci heap - a sequence of m decrease key and n delete min operations takes time O(m + n log n). A variant of relaxed heaps achieves similar bounds in the worst case- o(1) time for decrease key and O(log n) for delete min. A relaxed heap is a type of binomial queue that allows heap order to be violated. | |||||||||
Details der Publikation | |||||||||
| |||||||||