Relaxed Heaps: An Alternative to Fibronacci Heaps
Report ID: TR-109-87Author: Tarjan, Robert E. / Driscoll, James R. / Gabow, Harold N. / Shrairman, Ruth
Date: 1987-07-00
Pages: 19
Download Formats: |PDF|
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.