Lecture 25 – November 26, 2007
We took an array and turned it into a max heap
Then we added some elements to the array (i.e. increased its size) modifying the position of some of the values in order to maintain it as a max heap
We then performed a heap sort, swapping the root with the last unprocessed child and then re-heapified the array.
We discussed that a min heap would have each node’s value less than either of its children.
We reaffirmed that in spite of the amount of work it looked like we were doing, this is a n log n sort.
The remaining topics we want to cover this semester are graphs and hash tables.
A graph is a collection of nodes and edges
A graph may be a directed graph or an undirected graph.
We drew an undirected graph on the whiteboard.
The graph we drew had no cycles (loops).
Directed graphs may have “parallel” edges connecting a given node (one going to the node, one coming from the node).
Computer science graphs are used to
Find the shortest path in a graph (where the graph may be a map of an area to be covered by a postman, or a garbage collector)
Determine a path from a given place to a given place (where you might want to find an airline route between two places that are not directly connected).
The weights on an edge of a graph might represent (distance for the postman; cost for the airplane ticket).
Link to txt versions of Chapter 11 slides:
HOMEWORK
You should study all about graphs in chapter 11. There will be a quiz on the concepts and on the code (graph.adb, graph.ads).