Suggested Final Project Topics

Priority Queues from Sorting

Given a priority queue, it's easy to build a sorting algorithm: just enqueue everything into the priority

queue and then dequeue everything. It turns out that the converse is also possible – given a sorting algo-

rithm, it's possible to construct an efficient priority queue that's internally backed by that sorting algo-

rithm. There are a number of constructions that make this possible, most of which assume that the data

are integers and many of which use a number of clever techniques.