Advertisement
Published in:
2003 | OriginalPaper | Chapter
Distribution-Sensitive Binomial Queues
Author : Amr Elmasry
Published in: Algorithms and Data Structures
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A new priority queue structure is introduced, for which the amortized time to insert a new element is O(1) while that for the minimum-extraction is $O({\rm log} \bar{K})$. $\bar{K}$ is the average, taken over all the deleted elements x, of the number of elements that are inserted during the lifespan of x and are still in the heap when x is removed. Several applications of our structure are mentioned.