A new proof of the Garsia-Wachs algorithm |
| |
| Affiliation: | 1. Cardiac Catheterization Laboratory and Cardiology, ASST Spedali Civili di Brescia and Department of Medical and Surgical Specialties, Radiological Sciences, and Public Health, University of Brescia, Piazzale Spedali Civili, 1, Brescia 25123, Italy;2. National Centre for Global Health, Istituto Superiore di Sanità, Rome, Italy;3. Division of Cardiology, A.O.U. Policlinico “G. Rodolico – San Marco”, University of Catania, Catania, Italy;4. Clinica Montevergine, GVM Care & Research, Mercogliano, Italy;5. Heart and Lung Center, Helsinki University Hospital, University of Helsinki, Helsinki, Finland;6. Division of Cardiology, Department of Cardiac, Thoracic and Vascular Sciences, University of Padova, Padova, Italy;7. Italian National Agency for Regional Healthcare Services, Rome, Italy;8. Division of Cardiology, Centro Cuore Morgagni, Catania, Italy;9. Division of Cardiology, University of Parma, Parma, Italy;10. Campus Bio-Medico University of Rome, Rome, Italy;11. Anestesia e Rianimazione Dipartimento Cardiotoracovascolare, IRCSS Policlinico S.Orsola, Università degli Studi di Bologna, Bologna, Italy;1. Heart and Vascular Center, Semmelweis University, Budapest, Hungary;2. Department of Radiology, Medical Imaging Center, Semmelweis University, Budapest, Hungary |
| |
| Abstract: | A new proof of correctness for the Garsia-Wachs algorithm is presented. Like the well-known Hu-Tucker algorithm, the Garsia-Wachs algorithm constructs minimum cost binary trees in O(n log n) time. The new proof has a simpler structure and is free of the difficult inductions of the original. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
