| |
- 刊名: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.
| |
NGLC 2004-2010.National Geological Library of China All Rights Reserved.
Add:29 Xueyuan Rd,Haidian District,Beijing,PRC. Mail Add: 8324 mailbox 100083
For exchange or info please contact us via email.
| |