• Queaps

Treffer: Queaps

Title:
Queaps
Authors:
IACONO, John, LANGERMAN, Stefan
Source:
Annual International Symposium on Algorithms and ComputationAlgorithmica. 42(1):49-56
Publisher Information:
New York, NY: Springer, 2005.
Publication Year:
2005
Physical Description:
print, 18 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Arbre recherche binaire, Binary search tree, Arbol investigación binaria, File attente, Queue, Fila espera, Méthode arborescente, Tree structured method, Método arborescente, Structure donnée, Data structure, Estructura datos, Système FIFO, FIFO system, Sistema FIFO, Queaps, Structure donnée autoajustée, Data structures
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Department of Computer and Information Science, Polytechnic University, 5 MetroTech Center, Brooklyn, NY 11201, United States
Département d'informatique, Université Libre de Bruxelles, Avenue Franklin D. Roosevelt 50, 1050 Bruxelles, Belgium
ISSN:
0178-4617
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=16767888
Rights:
Copyright 2005 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.16767888
Database:
PASCAL Archive

Weitere Informationen

A new priority queue structure, the queap, is introduced. The queap executes insertion in O(1) amortized time and extract-min in O(log(k + 2)) amortized time if there are k items that have been in the heap longer than the item to be extracted. Thus if the operations on the queap are first-in first-out, as on a queue, each operation will execute in constant time. This idea of trying to make operations on the least recently accessed items fast, which we call the queueish property, is a natural complement to the working set property of certain data structures, such as splay trees and pairing heaps, where operations on the most recently accessed data execute quickly. However, we show that the queueish property is in some sense more difficult than the working set property by demonstrating that it is impossible to create a queueish binary search tree, but that many search data structures can be made almost queueish with a O(log log n) amortized extra cost per operation.