Paper Info
Title
Are Fibonacci Heaps Optimal?
Abstract
In this paper we investigate the inherent complexity of the priority queue abstract data type. We show that, under reasonable assumptions, there exist sequences of n Insert, n Delete, m DecreaseKeyand t FindMinoperations, where 1 ≤ t ≤ n, which have Ω(nlogt + n + m) complexity. Although Fibonacci heaps do not achieve this bound, we present a modified Fibonacci heap which does, and so is optimal under our assumptions.
Year
DOI
Venue
1994
10.1007/3-540-58325-4_210
ISAAC
Keywords
Field
DocType
fibonacci heaps optimal,abstract data type,priority queue
Abstract data type,Discrete mathematics,Combinatorics,Fibonacci heap,Shortest path problem,Heap (data structure),Priority queue,Time complexity,Mathematics,Fibonacci number,Double-ended priority queue
Conference
ISBN
Citations 
PageRank 
3-540-58325-4
5
0.59
References 
Authors
7
2
Name
Order
Citations
PageRank
Diab Abuaiadh1321.86
Jeffrey H. Kingston233638.79