treethere are more nodesand fewer potential bubble down stepsso the total number of operations will actually be much less than nlog to be sure of the complexity classwe need to perform more accurate calculation at each level of tree of height there will be nodeswith at most bubble down stepseach with comparisonsso the total number of comparisons for tree of height will on average be (hh ( = - = - = the final sum converges to as increases (see appendix )so for large we have ( = + and the worst case will be no more than twice that thusthe total number of operations is ( + ( )meaning that the complexity class of heapify is actually ( )which is better than the (nlog ncomplexity of inserting the items one at time merging binary heap trees frequently one needs to merge two existing priority queues based on binary heap trees into single priority queue to achieve thisthere are three obvious ways of merging two binary heap trees and of similar size into single binary heap tree move all the items from the smaller heap tree one at time into the larger heap tree using the standard insert algorithm this will involve moving (nitemsand each of them will need to be bubbled up at cost (log )giving an overall time complexity of (nlog repeatedly move the last items from one heap tree to the other using the standard insert algorithmuntil the new binary tree maketree( , ,sis complete then move the last item of the new tree to replace the dummy root " "and bubble down that new root how this is best done will depend on the sizes of the two treesso this algorithm is not totally straightforward on averagearound half the items in the last level of one tree will need moving and bubblingso that will be (nmoveseach with cost of (log )again giving an overall time complexity of (nlog nhoweverthe actual number of operations required willon averagebe lot less than the previous approachby something like factor of fourso this approach is more efficienteven though the algorithm is more complex simply concatenate the array forms of the heap trees and and use the standard heapify algorithm to convert that array into new binary heap tree the heapify algorithm has time complexity ( )and the concatenation need be no more than thatso this approach has (noverall time complexitymaking it in the best general approach of all three thusthe merging of binary heap trees generally has (ntime complexity