solve

. One of the problems with implementing Heap Sort in real life is its unfriendliness with the cache. One result is that in real computers it 1s much faster to swap list entries whose indices are close. Denote by C' the cache limit. Suppose that when we swap entries in indices x and y it takes time Hf if |a y| C but that is not important for the problem. Suppose we have a complete binary tree with levels indexed 0,..., 2 and we call maxheapify on the node with index 2' for some i. Moreover suppose that each swap is to the left, the node is swapped all the way to the bottom, and that there are sufficient levels that both cache hits and cache misses occur (this eliminates annoying special cases). Calculate the total swap time as a function of L,1,C,H,M. Simplify. Solution