Hollow Heaps

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9134
• 期：1
• 页码：689-700
• 全文大小：184 KB
• 参考文献：1.Brodal, G.S.: Worst-case efficient priority queues. In: Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 52鈥?8 (1996)
  2.Brodal, G.S., Lagogiannis, G., Tarjan, R.E.: Strict Fibonacci heaps. In: Proc. of the 44th ACM STOC, pp. 1177鈥?184 (2012)
  3.Chan, T.M.: Quake heaps: a simple alternative to fibonacci heaps. In: Brodnik, A., L贸pez-Ortiz, A., Raman, V., Viola, A. (eds.) Space-Efficient Data Structures, Streams, and Algorithms. LNCS, vol. 8066, pp. 27鈥?2. Springer, Heidelberg (2013)
  4.Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1, 269鈥?71 (1959)MATH MathSciNet View Article
  5.Driscoll, J.R., Gabow, H.N., Shrairman, R., Tarjan, R.E.: Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation. Communications of the ACM 31(11), 1343鈥?354 (1988)MathSciNet View Article
  6.Edmonds, J.: Optimum branchings. J. Res. Nat. Bur. Standards 71B, 233鈥?40 (1967)MathSciNet View Article
  7.Elmasry, A.: The violation heap: a relaxed Fibonacci-like heap. Discrete Math., Alg. and Appl. 2(4), 493鈥?04 (2010)
  8.Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34(3), 596鈥?15 (1987)MathSciNet View Article
  9.Gabow, H.N., Galil, Z., Spencer, T.H., Tarjan, R.E.: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6, 109鈥?22 (1986)MATH MathSciNet View Article
  10.Haeupler, B., Sen, S., Tarjan, R.E.: Rank-pairing heaps. SIAM Journal on Computing 40(6), 1463鈥?485 (2011)MATH MathSciNet View Article
  11.H酶yer, P.: A general technique for implementation of efficient priority queues. In: Proceedings of the 3rd Israeli Symposium on the Theory of Computing and Systems (ISTCS), pp. 57鈥?6 (1995)
  12.Kaplan, H., Shafrir, N., Tarjan, R.E.: Meldable heaps and boolean union-find. In: Proc. of the 34th ACM STOC, pp. 573鈥?82 (2002)
  13.Kaplan, H., Tarjan, R.E.: Thin heaps, thick heaps. ACM Transactions on Algorithms 4(1), 1鈥?4 (2008)MathSciNet View Article
  14.Kaplan, H., Tarjan, R.E., Zwick, U.: Fibonacci heaps revisited. CoRR, abs/1407.5750 (2014)
  15.Knuth, D.E.: Sorting and searching. The art of computer programming, vol. 3, 2nd edn. Addison-Wesley (1998)
  16.Peterson, G.L.: A balanced tree scheme for meldable heaps with updates. Technical Report GIT-ICS-87-23, School of Informatics and Computer Science, Georgia Institute of Technology, Atlanta, GA (1987)
  17.Prim, R.C.: Shortest connection networks and some generalizations. Bell System Technical Journal 36, 1389鈥?401 (1957)View Article
  18.Takaoka, T.: Theory of 2鈥? heaps. Discrete Appl. Math. 126(1), 115鈥?28 (2003)MATH MathSciNet View Article
  19.Tarjan, R.E.: Data structures and network algorithms. SIAM (1983)
  
• 作者单位：Thomas Dueholm Hansen (17)
  Haim Kaplan (18)
  Robert E. Tarjan (19) (20)
  Uri Zwick (18)
  
  17. Department of Computer Science, Aarhus University, Aarhus, Denmark
  18. Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv-Yafo, Israel
  19. Department of Computer Science, Princeton University, Princeton, NJ, 08540, USA
  20. Intertrust Technologies, Sunnyvale, CA, 94085, USA
  
• 丛书名：Automata, Languages, and Programming
• ISBN：978-3-662-47672-7
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

We introduce the hollow heap, a very simple data structure with the same amortized efficiency as the classical Fibonacci heap. All heap operations except delete and delete-min take O(1) time, worst case as well as amortized; delete and delete-min take \(O(\log n)\) amortized time. Hollow heaps are by far the simplest structure to achieve this. Hollow heaps combine two novel ideas: the use of lazy deletion and re-insertion to do decrease-key operations, and the use of a dag (directed acyclic graph) instead of a tree or set of trees to represent a heap. Lazy deletion produces hollow nodes (nodes without items), giving the data structure its name.