English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  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