notes there are exactly + nodes in the perfect left subtree from the inductive hypothesisthere are + nodes in the right subtree thusmk + + ( + )+ thereforeby induction mh + for all > which proves the upper bound it follows from theorem that there exists exactly one complete binary tree that contains exactly internal nodes for every integer > it also follows from theorem that the height of complete binary tree containing internal nodes is [log nwhy are interested in complete treesas it turns outcomplete trees have some useful characteristics for examplein the preceding you saw that the internal path length of treei the sum of the depths of all the internal nodesdetermines the average time for various operations complete binary tree has the nice property that it has the smallest possible internal path lengththeorem the internal path length of binary tree with nodes is at least as big as the internal path length of complete binary tree with nodes extbfproof consider binary tree with nodes that has the smallest possible internal path length clearlythere can only be one node at depth zero--the root similarlyat most two nodes can be at depth oneat most four nodes can be at depth twoand so on thereforethe internal path length of tree with nodes is always at least as large as the sum of the first terms in the series but this summation is precisely the internal path length of complete binary treesince the depth of the average node in tree is obtained by dividing the internal path length of the tree by ntheorem tells us that complete trees are the best possible in the sense that the average depth of node in complete tree is the smallest possible but how small is smallthat isis does the average depth grow logarithmically with the following theorem addresses this questiontheorem the internal path length of complete binary tree with nodes is log ( log ( log = extbfproof the proof of theorem is left as an exercise for the reader from theorem you may conclude that the internal path length of complete tree is ( log nconsequentlythe depth of the average node in complete tree is (log nimplementation binary heap is heap-ordered complete binary tree which is implemented using an array in heap the smallest key is found at the root and since the root is always found in the first position of the arrayfinding the smallest key is trivial operation in binary heap in this section we will describe the implementation of priority queue as binary heap as shown in figure define concrete class called binaryheap for this purpose lovely professional university