CPS 100, Spring 2004, Recitation March 22-23

Priority Queues

We discussed code in class similar to the code below for sorting using a priority queue void sort(tvector<string>& list) { tpqueue<string> pq; for(int k=0; k < list.size(); k++){ pq.insert(list[k]); } for(int k=0; k < list.size(); k++){ pq.deletemin(list[k]); } }
1. If tpqueue is implemented using a heap, what is the complexity of the code above and why?

2. If the heap is implemented using an unsorted vector (using pushback for insert, and search for finding min) what is the complexity of the sort and why?

   Priority Queues in Order

3. Instead of storing values in a tree and using tree functions, you can find the k-th largest value by inserting all values from a vector into a priority queue, then calling deletemin O(k) times to get first the smallest item from the priority queue, then the next smallest, and so on.

   This algorithm doesn't find just the single k-th smallest, it finds the smallest k elements and stores them in the vector. As a result, the vector might be much smaller than it was originally, e.g., if you find the 10 smallest elements in a 1000-element vector.

   This algorithm has two steps:

   • Insert all vector elements into the priority queue

   • Call deletemin k+1 times to get the values out of the priority queue (for example, you must call deletemin once when k = 0).

   Write the code using the class tpqueue. Assume the vector stores int values. Here's some example code to base yours on. tpqueue<int> pq; pq.insert(3); pq.insert(6); int value; pq.deletemin(value); // now value = 3 and pq contains one value, 6

   Complete the function below and determine what it's big-Oh complexity is assuming tpqueue is implemented using a heap.

   void qfindK(tvector<int>& a, int kVal) // pre: a has a.size() values, 0 <= kVal < a.size() // post: changes a so that a contains kVal+1 values, // these are in sorted order, and the values // are the kVal+1 smallest values in the vector passed in { tpqueue<int> pq; // insert all of a's elements into pq a.clear(); // a is empty, get the appropriate values from pq and store in a }

   Huffman Tree Questions

4. Consider the following characters and frequency of occurence.

   character	frequency	character	frequency
   'a'	5	't'	3
   's'	1	'o'	1
   'e'	8	'r'	2

   Draw the Huffman tree for these characters. Make a statement about the shape of the tree as a "good" Huffman tree as the shape is related to the frequencies which are from a Fibonacci sequence:

    1 1 2 3 5 8 13 21 ...
   

   where each number after the first two is the sum of the previous two numbers.

5. Consider a tree shaped like the one in the previous problem, but in which 256 different characters appear. How long is the longest encoding (such as 010010101..) for a character? The shortest encoding?