Black box for constant-time insertion in priority queues

Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

Abstract

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

Detaljer

Författare
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)
Originalspråkengelska
Sidor (från-till)102-106
TidskriftACM Transactions on Algorithms
Volym1
Utgivningsnummer1
StatusPublished - 2005
PublikationskategoriForskning
Peer review utfördJa