[ANU] [DCS] [COMP2100/2500] [Description] [Schedule] [Lectures] [Labs] [Homework] [Assignments] [COMP2500] [Assessment] [PSP] [Java] [Reading] [Help]

COMP2100/2500
Lecture 27: Data Structures IV

Summary

This lecture covers basic material about tree traversals using explicit stacks (preorder) and queues (breadth-first search), then, using Huffman codes and Huffman trees as motivation, introduces priority queues and . . . well, then, it gets completely out of hand. We show how priority queues can be implemented as heaps, and, in turn, how heaps can be implemented as left-justified complete binary trees stored in arrays. As a special treat, we see how heaps are used in the classic sorting algorithm known as Heapsort.

I wrote this lecture in 2004 but it was way too long, so this time I'll stop at the implementation of Huffman coding.

This material was based on lectures from COMP1110 as well as sections 6.4 and 8.1-8.4 of Jeffrey H. Kingston, Algorithms and Data Structures: Design, Correctness, Analysis, second edition, Addison-Wesley, 1997.

You can download the 2005 COMP2100 Lecture 27 as a PDF file. This is the cut-down version of the lecture using Java for 2005. Note that I have tried to match the original version as closely as possible. In practice, that means that references to classes such as Stack, Queue, and List are done in the Eiffel style, not using the interfaces and classes of those names that come with Java. (That's my excuse for now. I'll probably rewrite the code to use the Java versions.)

You can download the 2004 COMP2100 Lecture 11 as a PDF file. This is the complete original version of the lecture using Eiffel. All the secrets of priority queues, heaps, and Heapsort are revealed. If you compare the Java code with the Eiffel original you should pick up enough Eiffel to make sense of the remainder of the material.

Some questions answered

Q: You wrote the Queue constructor signature as public Queue(). Why not public<T> Queue()? A:We're both right (I think). When writing the class, I initially copied the name of the class, which is Queue<T>, to use as the constructor signature. So it looked like public Queue<T>() {...}. This definitely doesn't work. So I just took out the <T> part and it compiled - and worked just fine. I didn't think to try another combination. Certainly public<T> Queue() also compiles and works. Is there a difference? I looked (again) through Sun's tutorial Generics in the Java Programming Language and couldn't find a single example of a definition of a constructor of a generic class. How are you supposed to figure this out for yourself without some trial and error?

Q: What are breadth-first searches used for? A: I wanted to press on with the lecture rather than scratch my head for a few minutes. I invite you to have a look for yourself, but I'll offer one very important application area: games. Remember the game tree from Hexapawn? It was small enough that we could traverse all of it. Now imagine the game tree for chess. It's way too big to build all of it, and chess programs don't try. A basic implementation of a computer chess player has to limit the depth of the tree that can be searched, and it might prioritize subtrees for exploration by using a breadth-first search. Similar approaches are taken in other application areas in AI.

[ANU] [DCS] [COMP2100/2500] [Description] [Schedule] [Lectures] [Labs] [Homework] [Assignments] [COMP2500] [Assessment] [PSP] [Java] [Reading] [Help]