Implement a version of HeapManager with a best$-$fit mechanism. Start with a renamed copy of the HeapManager class, and then modify the allocate method to implement a best$-$fit search. $($The code for HeapManager is available on the Web site for this book. It includes the coalescing version of dea$1$locate, which is the one you should use.$)$

After this has been tested and works, find a simple sequence of operations for which your best$-$fit manager succeeds while the first$-$fit one fails. Hint: There is a sequence that begins like this:

$mm=$ new HeapManager $($new int $[7])$;

int $a=mm.$allocate $(2)$;

int $b=mm,$allocate $(1)$;

int $c=mm.$allocate $(1)$;

mm$.$ deallocate $(a)$;

mm$.$ deallocate $($c$)$ ;

By extending this sequence with just two more calls to mu$.$ allocate, you can get something that will succeed for best$-$fit and fail for first$-$fit.

Although best$-$fit is often a better placement strategy than first$-$fit, there are examples for which it is worse. Find a simple sequence of operations for which the first$-$fit manager succeeds while your best$-$fit one fails. Hint: There is a sequence that begins like this:

mim $=$ new HeapManager $($new int $[11])$ ;

$a=mi.$allocate $(4)$;

b $=mm.$allocate $(1)$;

$c=mm.$allocate $(3)$;

mm$.$ deallocate $(a)$;