The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Black box for constant-time insertion in priority queues

På svenska

Author

Summary, in English

We present a simple black box that takes a priority queue Q which supports find-min, insert, and delete in x-time at most t. Here x-time may be worst-case, expected, or amortized. The black-box transforms Q into a priority queue Q* that supports find-min in constant time, insert in constant x-time, and delete in x-time O(t). Moreover, if Q supports dec-key in constant time, then so does Q*.

Department/s

  • Computer Science

Publishing year

2005

Language

English

Pages

102-106

Publication/Series

ACM Transactions on Algorithms

Volume

1

Issue

1

Document type

Journal article

Publisher

Association for Computing Machinery (ACM)

Topic

  • Computer Science

Status

Published

ISBN/ISSN/Other

  • ISSN: 1549-6333