chap binary trees min-heaps and max-heaps both have their uses for examplethe heapsort of section uses the max-heapwhile the replacement selection algorithm of section uses min-heap the examples in the rest of this section will use max-heap be careful not to confuse the logical representation of heap with its physical implementation by means of the array-based complete binary tree the two are not synonymous because the logical view of the heap is actually tree structurewhile the typical physical implementation uses an array figure shows an implementation for heaps the class is generic with one type parameter defines the type for the data elements stored in the heap must extend the comparable interfaceand we use the compareto for comparing records in the heap this class definition makes two concessions to the fact that an array-based implementation is used firstheap nodes are indicated by their logical position within the heap rather than by pointer to the node in practicethe logical heap position corresponds to the identically numbered physical position in the array secondthe constructor takes as input pointer to the array to be used this approach provides the greatest flexibility for using the heap because all data values can be loaded into the array directly by the client the advantage of this comes during the heap construction phaseas explained below the constructor also takes an integer parameter indicating the initial size of the heap (based on the number of elements initially loaded into the arrayand second integer parameter indicating the maximum size allowed for the heap (the size of the arraymethod heapsize returns the current size of the heap isleaf(poswill return true if position pos is leaf in heap hand false otherwise members leftchildrightchildand parent return the position (actuallythe array indexfor the left childright childand parent of the position passedrespectively one way to build heap is to insert the elements one at time method insert will insert new element into the heap you might expect the heap insertion process to be similar to the insert function for bststarting at the root and working down through the heap howeverthis approach is not likely to work because the heap must maintain the shape of complete binary tree equivalentlyif the heap takes up the first positions of its array prior to the call to insertit must take up the first positions after to accomplish thisinsert first places at position of the array of coursev is unlikely to be in the correct position to move to the right placeit is compared to its parent' value if the value of is less than or equal to the value of its parentthen it is in the correct place and the insert