Abstract | ||
---|---|---|
We introduce a new representation of a priority queue in an array such that the operation of insert can be performed in constant time and minimum extraction in logarithmic time. In developing this structure we first introduce a very simple scheme permitting insertions in constant amortized time. This is modified to achieve the worst-case behavior using roughly lg*n pairs of pointers, and finally this pointer requirement is removed. |
Year | DOI | Venue |
---|---|---|
1988 | 10.1007/3-540-19487-8_1 | SWAT |
Keywords | Field | DocType |
constant insertion time,implicit binomial queue,priority queue | M/M/1 queue,Discrete mathematics,Combinatorics,G/G/1 queue,Multilevel queue,Computer science,Queue,Amortized analysis,M/G/1 queue,M/G/k queue,Priority queue | Conference |
Volume | ISSN | ISBN |
318 | 0302-9743 | 3-540-19487-8 |
Citations | PageRank | References |
27 | 1.63 | 8 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Svante Carlsson | 1 | 764 | 90.17 |
J. Ian Munro | 2 | 3010 | 462.97 |
Patricio V. Poblete | 3 | 232 | 50.10 |