Sorted dictionary and an application to priority queue

摘要

The paper studies a Dictionary type data structure with elements being sorted by their keys. The data structure Sorted Dictionary is clearly defined in the paper and an implementation is provided. Besides the O(logfl) time operations of searching, inserting, and deleting, a sorted dictionary can also provide efficient operations to manipulate the elements through their sorted order. The data structure is used to implement the generic Priority Queue, giving 0(1) time for removing the highest priority element while keeping ?(logn) time for other operations such as insert and delete.