Write a program to compare the running time of using the PriorityQueue’s one-parameter constructor to initialize the heap with N items versus starting with an empty PriorityQueue and performing N separate insertions. Run your program for sorted, reverse sorted, and random inputs.
Suppose that you have a number of boxes, each of which can hold total weight 1.0 and items i1, i2, i3, ..., iN, which weigh w1, w2, w3, ..., wN, respectively. The object is to pack all the items, using as few boxes as possible, without placing more weight in any box than its capacity. For instance, if the items have weights 0.4, 0.4, 0.6, and 0.6, you can solve the problem with two boxes. This problem is difficult, and no efficient algorithm is known. Several strategies give good, but not optimal, packings. Write programs to implement efficiently the following approximation strategies.
a. Scan the items in the order given; place each new item in the most-filled box that can accept it without overflowing. Use a priority queue to determine the box that an item goes in.
b. Sort the items, placing the heaviest item first; then use the strategy in part (a).