Data Structures, Algorithms, & Applications in C++
Chapter 13, Exercise 5

(a)

We replace the use of a winner tree with a min heap. The root of the min heap contains the next element to be output, either as part of the current run or as the first element of the next run. When the min element is output, it is replaced by the next element in the input. The replacement of the current min element with the next input element can be done efficiently using the change min operation which is the counterpart of the change max operation defined for max heaps in Exercise 12.12. Using a p element min heap, each element of a run can be produced in O(log p) time. This time includes the time to replace the next element in the run with a new element from the output. By comparison, the time required by a winner tree is Theta(log p).

(b)

When a winner tree is used, each element replacement requires log p element compares. When a min heap is used, this operation can take up to 2log p element compares. When element compares are expensive relative to other operations, the winner tree will have a better worst-case performance. When element compares are not expensive, we will need to program the two approaches and determine, experimentally, which is better.