Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Black box for constant-time insertion in priority queues

In English

Författare

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*.

Avdelning/ar

  • Computer Science

Publiceringsår

2005

Språk

Engelska

Sidor

102-106

Publikation/Tidskrift/Serie

ACM Transactions on Algorithms

Volym

1

Issue

1

Dokumenttyp

Artikel i tidskrift

Förlag

Association for Computing Machinery (ACM)

Ämne

  • Computer Science

Status

Published

ISBN/ISSN/Övrigt

  • ISSN: 1549-6333