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. If the index of a node is $n$, what is the index of its grandparent?

    $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 String instance variable uniqueSymbols to this end. Note that the java.util.Arrays package has been imported in the given code, so feel free to take advantage of the Arrays.sort() method to accomplish this task. 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:
    D : 01
    _ : 00
    a : 10
    b : 1111
    c : 1110
    e : 110
    
    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.)