Yifan
Zhang,
Master’s
candidate
David
R.
Cheriton
School
of
Computer
Science
Existing studies of priority queue implementations often focus on improving canonical operations such as insert and deleteMin, while sacrificing design simplicity and predictable worst case latency. Design simplicity is sacrificed as the algorithm becomes more and more optimized, taking into account characteristics of the input workload distribution. Predictable worst case latency is sacrificed when operations such as memory allocation and structural re-organization are deferred until absolutely necessary.
While these techniques often yield performance improvement to some degree, one might want to take a step back and ask a more basic question: is it possible to achieve similar performance while retaining a simple design? By combining techniques such as hierarchical bit vector and dynamic horizon resizing, all of which are straight-forward in principle, this thesis presents a new priority queue design called FlexQueue, that answers this question with a definitive “yes”.