Thin heaps, thick heaps

ABSTRACT

The Fibonacci heap was devised to provide an especially efficient implementation of Dijkstra's shortest path algorithm. Although asyptotically efficient, it is not as fast in practice as other heap implementations. Expanding on ideas of Høyer [1995], we describe three heap implementations (two versions of thin heaps and one of thick heaps) that have the same amortized efficiency as Fibonacci heaps, but need less space and promise better practical performance. As part of our development, we fill in a gap in Høyer's analysis.

REFERENCES

• 1: Adel'son-Vel'skii, G. M., and Landis, E. M. 1962. An algorithm for organization of information. Dokl. Akad. Nauk SSSR 146, 263--266.
• 2: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 3: Lars Arge , Michael A. Bender , Erik D. Demaine , Bryan Holland-Minkley , J. Ian Munro, Cache-oblivious priority queue and graph algorithm applications, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509950]
• 4: Bayer, R. 1972. Symmetric binary b-trees: Data structure and maintenance algorithms. Acta Inf. 1, 290--306.
• 5: Amir M. Ben-Amram, What is a “pointer machine”?, ACM SIGACT News, v.26 n.2, p.88-95, June 1995 [doi>10.1145/202840.202846]
• 6: Gerth Stølting Brodal, Worst-case efficient priority queues, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.52-58, January 28-30, 1996, Atlanta, Georgia, United States
• 7: Gerth Stølting Brodal, Fast Meldable Priority Queues, Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.282-290, August 16-18, 1995
• 8: Gerth Stølting Brodal , Rolf Fagerberg, Funnel Heap - A Cache Oblivious Priority Queue, Proceedings of the 13th International Symposium on Algorithms and Computation, p.219-228, November 21-23, 2002
• 9: Brodal, G. S., Fagerberg, R., Meyer, U., and Zeh, N. 2004. Cache-Oblivious data structures and algorithms for undirected breadth-first search and shortest paths. In Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT). Lecture Notes in Computer Science, vol. 3111. Springer, 480--492.
• 10: Brown, M. R. 1978. Implementation and analysis of binomial queue algorithms. SIAM J. Comput. 7, 3, 298--319.
• 11: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 12: James R. Driscoll , Harold N. Gabow , Ruth Shrairman , Robert E. Tarjan, Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation, Communications of the ACM, v.31 n.11, p.1343-1354, Nov. 1988 [doi>10.1145/50087.50096]
• 13: Elmasry, A. 2004a. Layered heaps. In Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT). Lecture Notes in Computer Science, vol. 3111. Springer.
• 14: Amr Elmasry, Parameterized self-adjusting heaps, Journal of Algorithms, v.52 n.2, p.103-119, August 2004 [doi>10.1016/j.jalgor.2004.03.002]
• 15: Michael L. Fredman, On the efficiency of pairing heaps and related data structures, Journal of the ACM (JACM), v.46 n.4, p.473-501, July 1999 [doi>10.1145/320211.320214]
• 16: Michael L. Fredman, A Priority Queue Transform, Proceedings of the 3rd International Workshop on Algorithm Engineering, p.243-257, July 19-21, 1999
• 17: Michael L. Fredman , Dan E. Willard, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, Journal of Computer and System Sciences, v.48 n.3, p.533-551, June 1994 [doi>10.1016/S0022-0000(05)80064-9]
• 18: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 19: Michael L. Fredman , Robert Sedgewick , Daniel D. Sleator , Robert E. Tarjan, The pairing heap: a new form of self-adjusting heap, Algorithmica, v.1 n.1, p.111-129, Jan. 1986 [doi>10.1007/BF01840439]
• 20: H N Gabow , Z Galil , T Spencer , R E Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, v.6 n.2, p.109-122, 1986 [doi>10.1007/BF02579168]
• 21: Guibas, L. J., and Sedgewick, R. 1978. A dichromatic framework for balanced trees. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), 8--21.
• 22: A general technique for implementation of efficient priority queues, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.57, January 04-06, 1995
• 23: Kaplan, H., and Tarjan, R. E. 1999. New heap data structures. Tech. Rep. TR-597-99, Princeton University.
• 24: Haim Kaplan , Nira Shafrir , Robert E. Tarjan, Meldable heaps and boolean union-find, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509990]
• 25: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 26: Peterson, G. L. 1987. A balanced tree scheme for meldable heaps with updates. Tech. Rep. GIT-ICS-87-23, School of Information and Computer Science, Georgia Institute of Technology, Atlanta, Georgia.
• 27: Seth Pettie, Towards a Final Analysis of Pairing Heaps, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.174-183, October 23-25, 2005 [doi>10.1109/SFCS.2005.75]
• 28: Daniel Dominic Sleator , Robert Endre Tarjan, Self adjusting heaps, SIAM Journal on Computing, v.15 n.1, p.52-69, Feb. 1986 [doi>10.1137/0215004]
• 29: John T. Stasko , Jeffrey Scott Vitter, Pairing heaps: experiments and analysis, Communications of the ACM, v.30 n.3, p.234-249, March 1987 [doi>10.1145/214748.214759]
• 30: Tadao Takaoka, Theory of 2-3 heaps, Discrete Applied Mathematics, v.126 n.1, p.115-128, March 2003 [doi>10.1016/S0166-218X(02)00219-6]
• 31: Tadao Takaoka, Theory of Trinomial Heaps, Proceedings of the 6th Annual International Conference on Computing and Combinatorics, p.362-372, July 26-28, 2000
• 32: Tarjan, R. E. 1979. A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. Syst. Sci. 18, 2, 110--127.
• 33: Tarjan, R. E. 1985. Amortized computational complexity. SIAM J. Algebr. Discrete Meth. 6, 2, 306--318.
• 34: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 35: Mikkel Thorup, Integer priority queues with decrease key in constant time and the single source shortest paths problem, Journal of Computer and System Sciences, v.69 n.3, p.330-353, November 2004 [doi>10.1016/j.jcss.2004.04.003]
• 36: Jean Vuillemin, A data structure for manipulating priority queues, Communications of the ACM, v.21 n.4, p.309-315, April 1978 [doi>10.1145/359460.359478]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS

General Terms:
Algorithms, Theory

Keywords:
Data structure, binomial queue, decrease key operation, fibonacci heap, heap, melding, priority queue, thick heap, thin heap