CSC 378: Data Structures and Algorithm Analysis

ABSTRACT DATA TYPES

Abstract Data Types

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

The Priority Queue ADT

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:

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

The Dictionary ADT

Each datum has a key.

There is a total order on the keys.

The dictionary stores the data and permits operations:

Dictionary Implementations

As a linked list of n elements

Insert takes index1.gif time (just add an element to the head of the list).

Search and delete take index2.gif time in a list of index3.gif elements (the whole list might have to be inspected).

As a Balanced Binary Search Tree

Balanced BSTs will be discussed in a later lecture. Their big advantage is that all operations take index4.gif time in a tree of index5.gif elements.




Back to the lecture index

Copyright 1998 James Stewart