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.A heap is represented as an array whose value at index $0$ is

`null`

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

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

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

grandparent index $= n/4$

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$.

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*). 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`java.util.Hashtable`

class -- so you don't have to write your own hash table class!`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.*)A full array of $16$ objects of class

`Widget`

is to be sorted using heapsort.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`Widget`

must implement what interface so that heapsort can be applied?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.

sinks only

`Comparable`

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

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.