| dbo:abstract |
In computer science, a queap is a priority queue data structure. The data structure allows insertions and deletions of arbitrary elements, as well as retrieval of the highest-priority element. Each deletion takes amortized time logarithmic in the number of items that have been in the structure for a longer time than the removed item. Insertions take constant amortized time. The data structure consists of a doubly linked list and a 2–4 tree data structure, each modified to keep track of its minimum-priority element. The basic operation of the structure is to keep newly inserted elements in the doubly linked list, until a deletion would remove one of the list items, at which point they are all moved into the 2–4 tree. The 2–4 tree stores its elements in insertion order, rather than the more conventional priority-sorted order. Both the data structure and its name were devised by John Iacono and Stefan Langerman. (en) |
| dbo:thumbnail |
wiki-commons:Special:FilePath/Queap.svg?width=300 |
| dbo:wikiPageID |
31075298 (xsd:integer) |
| dbo:wikiPageLength |
9955 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1076478474 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbc:Amortized_data_structures dbc:Algorithmic_information_theory dbr:Doubly_linked_list dbr:Stefan_Langerman dbr:Computer_science dbr:John_Iacono dbr:Priority_queue dbr:Tree_traversal dbr:Data_structure dbr:2–3–4_tree dbr:Amortized_analysis dbc:Heaps_(data_structures) dbc:Articles_with_example_Java_code dbr:Splay_tree dbr:Amortized_time dbr:Java_language dbr:Queue_(data_structure) dbr:File:Queap.svg |
| dbp:wikiPageUsesTemplate |
dbt:One_source dbt:Reflist |
| dct:subject |
dbc:Amortized_data_structures dbc:Algorithmic_information_theory dbc:Heaps_(data_structures) dbc:Articles_with_example_Java_code |
| gold:hypernym |
dbr:Structure |
| rdf:type |
dbo:Building |
| rdfs:comment |
In computer science, a queap is a priority queue data structure. The data structure allows insertions and deletions of arbitrary elements, as well as retrieval of the highest-priority element. Each deletion takes amortized time logarithmic in the number of items that have been in the structure for a longer time than the removed item. Insertions take constant amortized time. Both the data structure and its name were devised by John Iacono and Stefan Langerman. (en) |
| rdfs:label |
Queap (en) |
| owl:sameAs |
freebase:Queap wikidata:Queap dbpedia-fa:Queap dbpedia-la:Queap dbpedia-sr:Queap https://global.dbpedia.org/id/4taGB |
| prov:wasDerivedFrom |
wikipedia-en:Queap?oldid=1076478474&ns=0 |
| foaf:depiction |
wiki-commons:Special:FilePath/Queap.svg |
| foaf:isPrimaryTopicOf |
wikipedia-en:Queap |
| is dbo:wikiPageRedirects of |
dbr:Queaps |
| is dbo:wikiPageWikiLink of |
dbr:List_of_data_structures dbr:Stefan_Langerman dbr:Data_structure dbr:2–3–4_tree dbr:Queaps |
| is foaf:primaryTopic of |
wikipedia-en:Queap |
