TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

Priority Queue Classes with Priority Update

Tutkimustuotosvertaisarvioitu

Yksityiskohdat

AlkuperäiskieliEnglanti
OtsikkoSPLST 2015 Symposium on Programming Languages and Software Tools
AlaotsikkoProceedings of the 14th Symposium on Programming Languages and Software Tools (SPLST'15) Tampere, Finland, Oct 9-10, 2015
ToimittajatJyrki Nummenmaa, Outi Sievi-Korte, Erkki Mäkinen
KustantajaCEUR-WS.org
Sivut179-193
Sivumäärä15
Vuosikerta1525
TilaJulkaistu - 14 joulukuuta 2015
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaSYMPOSIUM ON PROGRAMMING LANGUAGES AND SOFTWARE TOOLS -
Kesto: 1 tammikuuta 1900 → …

Julkaisusarja

NimiCEUR Workshop Proceedings
Vuosikerta1525
ISSN (elektroninen)1613-0073

Conference

ConferenceSYMPOSIUM ON PROGRAMMING LANGUAGES AND SOFTWARE TOOLS
Ajanjakso1/01/00 → …

Tiivistelmä

A limitation in the design of the interface of C++ containers (i.e., data structure implementations) is addressed. Priority queues and their use in Dijkstra's shortest path search algorithm are used as an example. Priority queues are often implemented using heaps. There is a problem, however: it may be necessary to change the priority of an element while it is in the queue, but finding the element from within a heap is costly. The problem may be solved by keeping track, in a variable that is outside the heap, of the position of the element in the heap. Unfortunately, this is impossible with the template class interface used by the C++ standard library priority queue. In this research, the problem is analysed in detail. Three interface designs and the corresponding implementations are suggested. They are compared experimentally to each other and the C++ design.

Julkaisufoorumi-taso