When implementing the external heap property, it is important to notice that we can change the elements of a node without destroying the heap property, as long as the minimum element of the node does not become smaller. This allows siftdown to follow the path of children with the largest minimal element from the root towards the bottom of the heap, in a similar way as is done for the traditional heap.
A single iteration of the siftdown procedure (illustrated in figure 6.1) first merges the elements of the two childrens so that they become disjoint 2). This merge must ensure that the smallest element of the two nodes, remains in the same node as before the merge, so that the heap property of the subheaps are not violated. The next step then, is to merge the parent with the larger child 3).
Figure 6.1: The siftdown iteration
It is easily seen that this procedure defines a non-branching path from the root towards the bottom of the heap.- The sibling merge maintains the heap property in the two subheaps, and the parent/child merge only modifies one branch of the tree.
For siftdown to implement the merges efficiently, it is convenient that the nodes are kept sorted internally, which also allows easy access to both the smallest and the largest elements of a node. The cost of sorting the nodes internally imposes no extra overhead since at some point the elements in a node must be sorted anyway.
The siftdown procedure is listed in listing 6.1. It should be compared to the standard siftdown in listing 2.2. The procedures are strikingly similar!
The merge procedure used by siftdown merges the input so that the larger half of the elements goes to the node given by the first parameter.
The external cost of this siftdown procedure is clearly 
because this is the depth of the tree.
