sift down this best case scenario brings up good point if we could limit how far down the value is siftedwe might be able to speed up phase that' the topic or our next section the heapsort algorithm version in version onethe heapsort algorithm attained ( log ncomplexity during phase and phase ii in version twowe will be able to speed up phase of the heapsort algorithm up to (ncomplexity we do this by limiting how far each newly inserted value must be sifted down the idea is pretty simplebut yet powerful technique rather than inserting each element at the top of the heapwe'll build the heapor heapsfrom the bottom up this means that we'll approach the building of our heap by starting at the end of the list rather than the beginning an example will help make this more clear consider the list of values in fig that we wish to sort using heapsort rather than starting from the first element of the listwe'll start from the other end of the list there is no need to start with the last element as we will see we need to pick node that is parent of some node in the tree since the final heap is binary heapthe property we have is that half the nodes of the tree are leaf nodes and cannot be parents of any node within the heap we can compute the first parent index as follows parentindex (size )// the size above is the size of the list to be sorted note that because the list has indices to size- we must subtract two to compute the proper parentindex in all cases in this casethat parentindex is we need to start with index in the list to start building our heaps from the bottom up index will be the first parent and we'll sift it down as far as necessary fig list to be heapsorted this copy belongs to 'acha