Priority Queue Classes with Priority Update
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review
Details
| Original language | English |
|---|---|
| Title of host publication | SPLST 2015 Symposium on Programming Languages and Software Tools |
| Subtitle of host publication | Proceedings of the 14th Symposium on Programming Languages and Software Tools (SPLST'15) Tampere, Finland, Oct 9-10, 2015 |
| Editors | Jyrki Nummenmaa, Outi Sievi-Korte, Erkki Mäkinen |
| Publisher | CEUR-WS.org |
| Pages | 179-193 |
| Number of pages | 15 |
| Volume | 1525 |
| Publication status | Published - 14 Dec 2015 |
| Publication type | A4 Article in a conference publication |
| Event | Symposium on Programming Languages and Software Tools - Duration: 1 Jan 1900 → … |
Publication series
| Name | CEUR Workshop Proceedings |
|---|---|
| Volume | 1525 |
| ISSN (Electronic) | 1613-0073 |
Conference
| Conference | Symposium on Programming Languages and Software Tools |
|---|---|
| Period | 1/01/00 → … |
Abstract
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.