heaps howeverseveral tricks can make heapsort more efficient the first saves timeand the second saves memory trickling down in place if we insert new items into heapwe apply the trickleup(method times howeverall the items can be placed in random locations in the array and then rearranged into heap with only / applications of trickledown(this offers small speed advantage two correct subheaps make correct heap to see how this approach worksyou should know that trickledown(will create correct heap ifwhen an out-of-order item is placed at the rootboth the child subheaps of this root are correct heaps (the root can itself be the root of subheap as well as of the entire heap this is shown in figure if this is correct heapand this is correct heapthenif trickledown is applied to node athis will be correct heap figure both subheaps must be correct this suggests way to transform an unordered array into heap we can apply trickledown(to the nodes on the bottom of the (potentialheap--that isat the end of the array--and work our way upward to the root at index at each step the subheaps below us will already be correct heaps because we already applied trickledown(to them after we apply trickledown(to the rootthe unordered array will have been transformed into heap noticehoweverthat the nodes on the bottom row--those with no children--are already correct heapsbecause they are trees with only one nodethey have no relationships to be out of order thereforewe don' need to apply trickledown(to these nodes we can start at node / - the rightmost node with childreninstead of - the last node thuswe need only half as many trickle operations as we would using