Priority Queue Classes with Priority Update
Tutkimustuotos › › vertaisarvioitu
Yksityiskohdat
| Alkuperäiskieli | Englanti |
|---|---|
| Otsikko | SPLST 2015 Symposium on Programming Languages and Software Tools |
| Alaotsikko | Proceedings of the 14th Symposium on Programming Languages and Software Tools (SPLST'15) Tampere, Finland, Oct 9-10, 2015 |
| Toimittajat | Jyrki Nummenmaa, Outi Sievi-Korte, Erkki Mäkinen |
| Kustantaja | CEUR-WS.org |
| Sivut | 179-193 |
| Sivumäärä | 15 |
| Vuosikerta | 1525 |
| Tila | Julkaistu - 14 joulukuuta 2015 |
| OKM-julkaisutyyppi | A4 Artikkeli konferenssijulkaisussa |
| Tapahtuma | SYMPOSIUM ON PROGRAMMING LANGUAGES AND SOFTWARE TOOLS - Kesto: 1 tammikuuta 1900 → … |
Julkaisusarja
| Nimi | CEUR Workshop Proceedings |
|---|---|
| Vuosikerta | 1525 |
| ISSN (elektroninen) | 1613-0073 |
Conference
| Conference | SYMPOSIUM ON PROGRAMMING LANGUAGES AND SOFTWARE TOOLS |
|---|---|
| Ajanjakso | 1/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.