Programming Assignment 3 Computer Science 102

Spring 2002

Third draft due: to be announced in class


As discussed in draft#1, we are studying an efficient scheme for for compressing text files called Huffman coding. We again exploit the fact that not all characters appear with the same frequency in the text, by encoding rarely used characters with long codes and frequently used ones with short codes.

Given a set of characters and their corresponding frequencies, an optimal coding scheme is produced by Huffman coding. It uses a binary tree for encoding. In Draft #3, however, we use a heap as a priority queue instead of a linked list. The big Oh behavior for constructing a heap is O(nlog(n)); whereas, its O(n^2) for a list

Draft #3

We will use a heap implementation of a priority queue to this program. Note that here we use a min-heap in this project instead of the max-heap we used in class. Also, deleteMin() will replace the deleteMax() that is on the lecture links on the web. Here is the skeleton of the class you will be using:

public class Hw3c 
//solves draft #3 for project #3 
     static int last;
//the # of nodes in heap. This decreases as succesive pairs of
//minimum nodes are extracted
    final int MAX = 11;//there are 11 pairs of letter-frequency entries

   static Comparable x = new Comparable[MAX + 1]//one more element for shift up

    private class HuffRecord//defines the data frequency record
    {  public String letter; 
       public int freq;
    private class TreeNode implements Comparable
//defines the treelets comprising the list
   {  public HuffRecord data;
      public TreeNode left, right;

where HuffRecord and TreeNode are embedded classes. The keyword public is optional because it is the default. The class TreeNode must of course contain a compareTo method and should also contain a toString() method. Here are the methods to be added to your class of draft #2:

  1. initialize( HuffRecord[] stream) assigns the two fields of stream[], i.e., freq and letter to the corresponding fields of an instance of TreeNode, let's say aux. It assigns this to an element of an array of Comparable, x[]. This array is an instance variable which represents the heap.
  2. Method write prints the elements of the array x. In order to do this, you must of course cast x[j] as an instance of TreeNode and then dereference it before you print it, or you may use the implicit toString() method

  3. method shift(int m) shifts the elements one position, so that parent =child/2 has meaning.

  4. Method build creates a heap by calling shiftUp(j) in a loop. To facilitate your understanding of the heap process let's call shiftUp(j) by the name insert instead.

  5. Method reduceIt() calls reduce in a while loop while an instance variable last is greater than one. last represents the value of the highest subscript of the heap as the heap is shrunken,

  6. private void reduce() is similar to the method of the same name in draft #2. It
  7. private void combine(TreeNode p1, TreeNode p2) creates a new instance aux of TreeNode as in draft #2 whose frequency field is the sum of the frequencies in the objects pointed to by p1 and p2, and assigns aux to x[last]. Then places the element in its proper place in the heap by calling insert(last).

  8. private Comparable deleteMin(int n) swaps the top of the heap, the first element in x[], with the last element in it. It then reheapifies the heap by calling shiftDown(n-1). This method is defined in the heap sort done in class.

Each procedure should contain preconditions and postconditions. The data for this program is the same as for draft #2.

Your main method should:

The output for forming the heap is on the WEB. In the output, X is the character placed in the letter field for elements produced by combining two other elements.