Write a program that implements these heurisitics in an efficient manner to find out how many bins are required for a random sequence of N weights in the range 0 to u, using a priority queue ADT. Your task is to design an interface, build two different implementations for the ADT, and write two client programs, one for each of the two heuristics. Your client programs should take N and u as command-line arguments so that, for example, a.out 100 .2 will generate 100 random weights between 0 and .2 and print out the total of the weights generated (best possible number of bins) and the number of bins resulting from applying the heuristic.
Design an interface that is suited for this task, not necessarily a general-purpose priority queue interface. That is, figure out precisely which operations are needed by the client programs to complete the task, then provide implementations for those. You certainly will need the insert and delete the maximum operations, and for worst-fit decreasing, you should use the ADT operations to do the sort (you may use an auxiliary array).
The implementations of ADTs given in the book differ slightly from those given in lecture in that the latter leave the types of items in the data structure unspecified. You should do so in your implementations, specifying the type of items for the ADT only in the interface. Doing this properly will require some thought (and perhaps a few iterations on the problem).
First, design (and perhaps implement) the client programs to get an idea of which priority queue operations would be most convenient. Decide what type of data should go on the priority queue, what data structures are needed by the client, and so forth.
Second, develop an ordered array implementation for the ADT, which you can use to implement and debug the client program for the worst fit heuristic. After getting that working, do the other client program. Run both client programs for N=16 and u=.2 and .7, and print out the weights generated and the contents of the bins in some reasonable format.
Next, provide a heap-based implementation for the ADT. Your goal is to be able to do this without changing either client program or the interface at all. Run the client programs for the same values of N and u to make sure that the two priority queue implementations produce the same results.
Using the heap-based implementation, run both client programs for N= 100, 1000, 10000, and 100000. Do a few trials for each value with u=.2 and u=.7. In your writeup, comment on the relative effectiveness of the two heuristics.
Extra Credit. Find a heuristic that beats these two consistently for N=100000.