If you were lost on a desert island, what one ADT would you like to have with you?
Nell B. Dale · ACM SIGCSE Bulletin · 1990
Our answer to the question in the title is the abstract data type (ADT) priority queue, the workhorse of data types.We can make it do the work of a stack and a FIFO queue, we can use it to simulate other structures in classic algorithms, and we can implement it so that the operations are no worse than O(logN).In this paper we will look at the ADT priority queue from three perspectives: specification, implementation, and application.We specify its behavior using an abstract model, analyze alternate implementations using Big-O notation, and use it to implement four classic graph algorithms, SPECIFICATION OF ADT PRIORITY QUEUEThere are two techniques currently used to specify abstract data types: axiomatic specifications and abstract models.We use an abstract model because it is the more familiar technique.'Abstract modelling uses the operations of one abstract data type (called the underlying model) to describe the semantics of another abstract data type.The underlying model must be a well-defined mathematical data type or an abstract data type that has previously been defined axiomatically.Here, we use a bag (a multiset) as the underlying model in the specification of the ADT priority queue PQ of type PQType.