Exercises - Heaps and Priority Queues

  1. Suppose one implements a priority queue with an ordered array. Ignoring array resizing, what is the worst-case running-time cost for inserting items into the priority queue? ...for removing the maximum element? (You may of course assume that larger values correspond to a larger priority)

    Finding the position to insert an item can be quick (i.e., $O(\ln n$)). However, after having found the correct position, one still needs to make room in the array for the insertion. This requires moving all values greater than the one to be inserted each down one position in the array. In the worst case, we must insert the item at the beginning of the array, which then requires $O(n)$ exchanges to move everything else down one position.

    Removing the maximum element, however, can be fast. Presuming the array is stored where lower indices correspond to smaller values, one only has to grab a reference to the last element, assign this array position the value of null, and update instance variables storing the starting position of collection elements and the count of elements in the array. By itself, this has cost $O(1)$. There will occasionally need to be calls made to resize the array (and start the collection back at index 0), which will up the cost a bit, of course. However, these can be spaced out (at the expense of space cost) so the amortized cost is small.

  2. A heap is represented as an array whose value at index $0$ is null.

    1. Find the index of both the parent and right child of the element at index $21$.

    2. If the index of a node is $n$, what is the index of its grandparent?

    1. parent index $= 10$; right child index $= 43$

    2. grandparent index $= n/4$

  3. Write a class PriorityQueue whose implementation uses resizing arrays and supports the following methods:

    • void insert(Item item)
    • Item deleteMax()
    • Item deleteMin()
    • Item max()
    • Item min()

    For a priority queue object of this class consisting of $n$ items, the time complexity of the first three methods above should be $\sim \ln n$, while the last two should be $\sim 1$.

  4. Complete the class HuffmanEncoder.java whose constructor conducts a frequency analysis of the characters appearing in a given string and builds the corresponding Huffman tree for these characters using the MinPriorityQueueHeap class.

    When fleshing out the aforementioned constructor, add code to store all of the unique symbols encountered in the string passed to the constructor. Use the Hashtable instance variable uniqueSymbolCount to this end (Note, this is the java.util.Hashtable class -- so you don't have to write your own hash table class!). Then, add code to the remaining methods so that this Huffman tree can be used to encode and decode strings of text with similar symbol frequencies. The given main() method can be used to test your code. Do not add any additional instance variables or methods to the HuffmanEncoder.java class beyond those already provided.

    Upon execution -- as seen in the sample run below -- the codes constructed should be printed; the original message should be encoded with these codes with the result printed; and then this encoded message should decoded back to the original message (to verify a "lossless" encoding). The given code will also print a comparison of how many bits both the original and encoded versions of the message require for storage.

    $ java HuffmanEncoder↵
Enter a string to serve as the basis for the Huffman Coding:
A_DEAD_DAD_CEDED_A_BAD_BABE_A_BEADED_ABACA_BED

Codes Used:
A : 10
_ : 00
E : 110
D : 01
C : 1110
B : 1111

String provided can be encoded in 115 bits (+ code information)
1000011101001000110010011101100111001001000111110010011111011111100010001111110100111...

Decodes as: A_DEAD_DAD_CEDED_A_BAD_BABE_A_BEADED_ABACA_BED
Note, this would have required 368 bits to store in ASCII characters

    (Note, the entirety of the encoded bitstring that results is not shown above, given its length.)

  5. A full array of $16$ objects of class Widget is to be sorted using heapsort.

    1. When applying a heapsort to this array, which of the following are needed?
      i) sinks only   ii) swims only &   iii) both sinks and swims   iv) no sinks or swims

    2. Widget must implement what interface so that heapsort can be applied?

    3. At each stage of the heapsort, the array can be visualized as a binary tree -- although initially it is not necessarily in heap order. Before anything has moved as a result of the sort, find the index of the left child of the element at index 7 in the array.

    1. sinks only

    2. Comparable

    3. $2(7+1)-1 = 15$

  6. Assume a method less(i,j) is defined so that it returns true when the object at position i in an array should be considered "less than" the object at position j, and a method exch(i,j) is defined so that it swaps the objects at positions i and j in the array. Using these methods, write an implementation of swim(int k) that can be used to complete the insertion of an item put into a max-heap initially at position size+1 in the corresponding array, where size is the number of items in the heap before this insertion.

    See the notes.