Campus Event Calendar
Event Entry
What and Who
Pairing Heaps with O(log log) decrease Cost
Amr Elmasry
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG1 member (researcher on an AvH fellowship).
AG 1, AG 3, AG 5, SWS, AG 2, AG 4, RG1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 16 December 2008
14:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We give a variation of the pairing heaps for which the time bounds for all the operations match the lower bound proved by Fredman for a family of similar self-adjusting heaps. Namely, our heap structure requires $O(1)$ for insert and find-min, $O(\log{n})$ for delete-min, and $O(\log\log{n})$ for decrease-key and meld.
[This is a dry-run for the talk I will give at SODA 09.]
[This is a dry-run for the talk I will give at SODA 09.]
Contact
Amr Elmassry
116
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Algorithms; Data Structures; Heaps; Priority Queues; Self-Adjusting Structures; Amortized Analysis
Amr Elmassry, 12/08/2008 19:34
Amr Elmassry, 12/08/2008 19:32 -- Created document.
Amr Elmassry, 12/08/2008 19:32 -- Created document.