An ADT is a description of the interface to a collection of data. An ADT may have many implementations.

ADT	Implementation	Slowest Operation
Priority Queue	Array Heap Linked list	O( log n ) O( n )
Mergeable Heap	Leftist Tree Binomial Heap Array Heap with an additional 'Merge' procedure	O( log n ) O( log n ) O( n )
Dictionary	Linked List Binary Search Tree ( BST ) Balanced BST Skip List	O( n ) O( n ) O( log n ) O( log n ) expected

Each datum x has a "key" by which we refer to it, called "key(x)".

There is a total order on the keys.

The priority queue stores the data and permits operations:

• Insert datum
• Delete and return datum of max (or min) key
• Return datum of max (or min) key

For example, in C++:

Conceptually, a series of commands on a queue sorted by priority:

Command	Resulting queue
add 5 add 1 add 7 delmax delmax add 2 delmax	5 5 1 7 5 1 5 1 1 2 1 1

Each datum has a key.

There is a total order on the keys.

The dictionary stores the data and permits operations:

• Insert datum x
• Delete datum having key k
• Search for and return datum having key k

Dictionary Implementations