English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Pairing Heaps with O(log log n) decrease Cost

Elmasry, A. (2009). Pairing Heaps with O(log log n) decrease Cost. In 20th ACM-SIAM Symposium on Discrete Algorithms (pp. 471-476). Philadelphia, PA: SIAM.

Item is

Files

show Files
hide Files
:
paper.pdf (Any fulltext), 116KB
 
File Permalink:
-
Name:
paper.pdf
Description:
-
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Elmasry, Amr1, Author              
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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 (all the bounds are in the amortized sense except for find-min).

Details

show
hide
Language(s): eng - English
 Dates: 2009-04-072009
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 518315
DOI: 10.1137/1.9781611973068.52
Other: Local-ID: C1256428004B93B8-55CEC128573A3E0CC12575600061DE33-Elmasry2009
 Degree: -

Event

show
hide
Title: 20th ACM-SIAM Symposium on Discrete Algorithms
Place of Event: New York, NY, USA
Start-/End Date: 2009-01-04 - 2009-01-06

Legal Case

show

Project information

show

Source 1

show
hide
Title: 20th ACM-SIAM Symposium on Discrete Algorithms
  Abbreviation :
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Philadelphia, PA : SIAM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 471 - 476 Identifier: ISBN: 978-0-89871-680-1