on priority queue that never has more than elements simple implementation of the priority queueusing listwould give an ( algorithm the choice of priority queue implementation depends on how large is in the typical case of an ascii character setc is small enough that the quadratic running time is acceptable in such an applicationvirtually all the running time will be spent on the disk / required to read the input file and write out the compressed version there are two details that must be considered firstthe encoding information must be transmitted at the start of the compressed filesince otherwise it will be impossible to decode there are several ways of doing thissee exercise for small filesthe cost of transmitting this table will override any possible savings in compressionand the result will probably be file expansion of coursethis can be detected and the original left intact for large filesthe size of the table is not significant the second problem is thatas describedthis is two-pass algorithm the first pass collects the frequency dataand the second pass does the encoding this is obviously not desirable property for program dealing with large files some alternatives are described in the references approximate bin packing in this sectionwe will consider some algorithms to solve the bin-packing problem these algorithms will run quickly but will not necessarily produce optimal solutions we will provehoweverthat the solutions that are produced are not too far from optimal we are given items of sizes sn all sizes satisfy si < the problem is to pack these items in the fewest number of binsgiven that each bin has unit capacity as an examplefigure shows an optimal packing for an item list with sizes there are two versions of the bin packing problem the first version is online bin packing in this versioneach item must be placed in bin before the next item can be processed the second version is the offline bin packing problem in an offline algorithmwe do not need to do anything until all the input has been read the distinction between online and offline algorithms was discussed in section figure optimal packing for