with the highest priority appears in [nremoving this item would be very simplebut inserting new item would always involve finding the right position and shifting number of items to the right to make room for it for exampleinserting into the queue [ ] [ [ [ that kind of item insertion is effectively insertion sort and clearly inefficient in generalof (ncomplexity rather than (log nwith binary heap tree another approach would be to use an unsorted array in this casea new item would be inserted by just putting it into [ + ]but to delete the entry with the highest priority would involve having to find it first thenafter thatthe last item would have to be swapped into the gapor all items with higher index 'shifted downagainthat kind of item deletion is clearly inefficient in generalof (ncomplexity rather than (log nwith heap tree thusof those three representationsonly one is of use in carrying out the above idea efficiently an unsorted array is what we started fromso that is not any helpand ordering the array is what we are trying to achieveso heaps are the way forward to make use of binary heap treeswe first have to take the unsorted array and re-arrange it so that it satisfies the heap tree priority ordering we have already studied the heapify algorithm which can do that with (ntime complexity then we need to extract the sorted array from it in the heap treethe item with the highest prioritythat is the largest itemis always in [ in the sorted arrayit should be in the last position [nif we simply swap the twowe will have that item at the right position of the arrayand also have begun the standard procedure of removing the root of the heap-treesince [nis precisely the item that would be moved into the root position at the next step since [nnow contains the correct itemwe will never have to look at it again insteadwe just take the items [ ], [ - and bring them back into heap-tree form using the bubble down procedure on the new rootwhich we know to have complexity (log nnow the second largest item is in position [ ]and its final position should be [ - ]so we now swap these two items then we rearrange [ ], [ - back into heap tree using the bubble down procedure on the new root and so on when the ith step has been completedthe items [ - + ], [nwill have the correct entriesand there will be heap tree for the items [ ], [ -inote that the sizeand therefore the heightof the heap tree decreases at each step as part of the ith stepwe have to bubble down the new root this will take at most twice as many comparisons as the height of the original heap treewhich is log so overall there are stepswith at most log comparisonstotalling ( )log the number of comparisons will actually be less than thatbecause the number of bubble down steps will usually be less than the full height of the treebut usually not much lessso the time complexity is still (nlog nthe full heapsort algorithm can thus be written in very simple formusing the bubble down and heapify procedures we already have from first heapify converts the