M.Sc. Thesis by Asger Bruun (September 2010)
In this thesis, combinations of heap structures and heap stores in the designs of J. Vuillemin, M.R. Brown, and the CPH STL (Copenhagen Standard Template Library) on addressable meldable priority queues are investigated and the components are further developed. The objective was to attain an effective combination in a clean way in the program-library setting.
We participated at the 9th International Symposium on Experimental Algorithms held in May 2010 in Italy and confirmed in an experimental study that the CPH STL weak queue was performance-wise competitive. The results are published in the article "Policy-based benchmarking of weak heaps and their relatives", which is included in this thesis.
The two-pointer structures by M.R. Brown consume one pointer less per element than the ordinary three-pointer perfect weak-heap substructure and are able to execute at almost comparable speed. The work of M.R. Brown furthermore contains interesting space-optimization opportunities for a generic program library, like the CPH STL, offering fast algorithms and compact data structures.
Generic policies play an important role in the design of the CPH STL. Constructive criticism is raised against its current way of specifying generic policies and possible solutions to some of the existing problems are proposed.
In conclusion, the study showed that the more complex two-pointer structures, although effective, should be only used in cases where these structures save more storage than the space of a single pointer per element, i.e. when the structures achieve a better memory alignment.
The following files are available for download: