Lecture 19. 



I finished up our treatment of heaps today. We saw the moveUp and moveDown routines and how they can be used to build a heap from scratch.
The climax of our treatment of heaps showed how a heap can be built from scratch in linear time.

The next topic for discussion, is the map abstract data type. I briefly discussed the STL implementation of maps. This relates both to the Huffman C++ homework we have and our next topic, hashing and hash tables.

A simple example of the use of a map can be found here. You can obtain further information on maps and other classes in the STL in chapter 19 of Walter Savitch Absolute C++, Addison-Wesley Pub. Co., 2005 (2nd Edition).
I used a map in my version of the Huffman assignment. I have attached the code for your reference. Huffman.cpp

A hash table is a practical implementation of a map. The primary issues that we will discuss are some hashing functions, and collision resolution schemes.


 

Posted: Mon - February 26, 2007 at 12:38 PM          

©