figure leftafter percolatedown( )rightafter percolatedown( sh ( ii= ( ( ( ( - ( ( multiplying by gives the equation ( ( ( ( ( we subtract these two equations and obtain equation ( we find that certain terms almost cancel for instancewe have ( ( ( and so on the last term in equation ( ) does not appear in equation ( )thusit appears in equation ( the first term in equation ( )hdoes not appear in equation ( )thus- appears in equation ( we obtain - - ( + ( ( which proves the theorem complete tree is not perfect binary treebut the result we have obtained is an upper bound on the sum of the heights of the nodes in complete tree since complete tree has between and + nodesthis theorem implies that this sum is ( )where is the number of nodes although the result we have obtained is sufficient to show that buildheap is linearthe bound on the sum of the heights is not as strong as possible for complete tree with nodesthe bound we have obtained is roughly the sum of the heights can be shown by induction to be ( )where (nis the number of in the binary representation of applications of priority queues we have already mentioned how priority queues are used in operating systems design in we will see how priority queues are used to implement several graph algorithms efficiently here we will show how to use priority queues to obtain solutions to two problems