fig heap with elements fig key sifting through the heap let us now assume that heap with elements hl+ hr is given for some values and rand that new element has to be added to form the extended heap hl hr takefor examplethe initial heap shown in fig and extend the heap to the left by an element new heap is obtained by first putting on top of the tree structure and then by letting it sift down along the path of the smaller comparandswhich at the same time move up in the given example the value is first exchanged with then with and thus forming the tree shown in fig we now formulate this sifting algorithm as followsij are the pair of indices denoting the items to be exchanged during each sift step the reader is urged to convince himself that the proposed method of sifting actually preserves the heap invariants that define heap neat way to construct heap in situ was suggested by floyd it uses the sifting procedure shown below given is an array hn- clearlythe elements hm hn- (with div form heap alreadysince no two indices ij are such that + or + these elements form what may be considered as the bottom row of the associated binary tree (see fig among which no ordering relationship is required the heap is now extended to the leftwhereby in each step new element is included and properly positioned by sift this process is illustrated in table and yields the heap shown in fig procedure sift (lrinteger)var ijintegerxitembegin :lj : * + : [ ]if ( ( [ + [ ]then : + endwhile ( < ( [jxdo [ : [ ] :jj : * if ( ( [ + [ ]then : + end enda[ : end sift table constructing heap