Tyck till om SwePub Sök
här!
Sökning: onr:"swepub:oai:lup.lub.lu.se:11595432-2c98-455a-8d7d-58507e86fa01" >
Black box for const...
Black box for constant-time insertion in priority queues
-
Alstrup, Stephen (författare)
-
- Husfeldt, Thore (författare)
- Lund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Computer Science,Faculty of Science
-
Rauhe, Theis (författare)
-
visa fler...
-
Thorup, Mikkel (författare)
-
visa färre...
-
(creator_code:org_t)
- 2005-07
- 2005
- Engelska.
-
Ingår i: ACM Transactions on Algorithms. - : Association for Computing Machinery (ACM). - 1549-6333 .- 1549-6325. ; 1:1, s. 102-106
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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*.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas