Pairing Heaps with Costless Meld
| dc.creator | Elmasry, Amr | |
| dc.date | 2009-03-24 | |
| dc.date | 2009-04-09 | |
| dc.date.accessioned | 2026-07-07T13:01:35Z | |
| dc.date.available | 2026-07-07T13:01:35Z | |
| dc.description | Improving the structure and analysis in \cite{elm0}, we give a variation of the pairing heaps that has amortized zero cost per meld (compared to an $O(\log \log{n})$ in \cite{elm0}) and the same amortized bounds for all other operations. More precisely, the new pairing heap requires: no cost per meld, O(1) per find-min and insert, $O(\log{n})$ per delete-min, and $O(\log\log{n})$ per decrease-key. These bounds are the best known for any self-adjusting heap, and match the lower bound proved by Fredman for a family of such heaps. Moreover, the changes we have done make our structure even simpler than that in \cite{elm0}. | |
| dc.description | 10 pages, 2 figures | |
| dc.identifier | https://arxiv.org/abs/0903.4130 | |
| dc.identifier | http://arxiv.org/abs/0903.4130 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/226198 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Pairing Heaps with Costless Meld | |
| dc.type | text |