concept swap in category algorithms

This is an excerpt from Manning's book Algorithms and Data Structures in Action MEAP V14. Login to get full access to this book.

Listing 2.3 shows the improved version of the bubbleUp method: notice how, at some point, there will momentarily be two copies of the element originally at index [3] (and later, of the element at index [1]): this is because instead of actually swapping elements, we can just overwrite current element with its parent at each iteration (line #6) and only at the end we write the element bubbling up just once, as the last action in the method. This works because bubbling up an element is conceptually equivalent to the inner loop of insertion sort: we are looking for the right position to insert current element into the path connecting it to heap’s root.

If we start at the last internal node for the heap, let’s call it X, it will have at most 2, children, both leaves, and hence both valid heaps.

Figure 2.12 Heapification of a small array. The red boxes surround valid sub-heaps, i.e. portions of the tree for which we have verified that they abide by the heap properties.
(Step 1) Initially, only leaves are valid min-heap: here smaller numbers mean higher priority.
(Step 2) The element from which we start our iteration is the first internal node in the heap, at index 2 in our array. In the bottom part of the leftmost figure, it is pointed at by a red arrow. We repair the heap properties for the sub-heap rooted at this node by swapping its content with its child’s.
(Step 3) We move our red arrow one position to the left, and repeat the operation for the sub-heap rooted at index 1.
(Step 4) Finally, the whole array is heapified, by pushing down the temporary root (with priority 5) until we find its right place.

Listing 2.9 The heapify method

function heapify(pairs)
  for index in {(|pairs|-1)/D .. 0} do                                        #1
    pushDown(pairs, index)                                                    #2

copy