Tampere University of Technology

TUTCRIS Research Portal

Priority Queue Classes with Priority Update

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Details

Original languageEnglish
Title of host publicationSPLST 2015 Symposium on Programming Languages and Software Tools
Subtitle of host publicationProceedings of the 14th Symposium on Programming Languages and Software Tools (SPLST'15) Tampere, Finland, Oct 9-10, 2015
EditorsJyrki Nummenmaa, Outi Sievi-Korte, Erkki Mäkinen
PublisherCEUR-WS.org
Pages179-193
Number of pages15
Volume1525
Publication statusPublished - 14 Dec 2015
Publication typeA4 Article in a conference publication
EventSymposium on Programming Languages and Software Tools -
Duration: 1 Jan 1900 → …

Publication series

NameCEUR Workshop Proceedings
Volume1525
ISSN (Electronic)1613-0073

Conference

ConferenceSymposium on Programming Languages and Software Tools
Period1/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.

Publication forum classification

Field of science, Statistics Finland