we could have implemented the percolation in the insert routine by performing repeated swaps until the correct order was establishedbut swap requires three assignment statements if an element is percolated up levelsthe number of assignments performed by the swaps would be our method uses assignments if the element to be inserted is the new minimumit will be pushed all the way to the top at some pointhole will be and we will want to break out of the loop we could do this with an explicit testor we can put copy of the inserted item in position in order to make the loop terminate we elect to place into position the time to do the insertion could be as much as (log )if the element to be inserted is the new minimum and is percolated all the way to the root on averagethe percolation terminates earlyit has been shown that comparisons are required on average to perform an insertso the average insert moves an element up levels deletemin deletemins are handled in similar manner as insertions finding the minimum is easythe hard part is removing it when the minimum is removeda hole is created at the root since the heap now becomes one smallerit follows that the last element in the heap must move somewhere in the heap if can be placed in the holethen we are done this is unlikelyso we slide the smaller of the hole' children into the holethus pushing the hole down one level we repeat this step until can be placed in the hole thusour action is to place in its correct spot along path from the root containing minimum children in figure the left figure shows heap prior to the deletemin after is removedwe must now try to place in the heap the value cannot be placed in the holebecause this would violate heap order thuswe place the smaller child ( in the holesliding the hole down one level (see fig we repeat this againand since is larger than we place into the hole and create new hole one level deeper we then place in the hole and create new hole on the bottom level sinceonce again is too large finallywe are able to place in the hole (fig this general strategy is known as percolate down we use the same technique as in the insert routine to avoid the use of swaps in this routine frequent implementation error in heaps occurs when there are an even number of elements in the heapand the one node that has only one child is encountered you must figure creation of the hole at the root