reset password
Author Message
G190852562
Posts: 162
Posted 14:27 Dec 08, 2014 |

1. Assume one is using two heaps to keep track of the median of a sequence of numbers. Assume the "low" heap contains 11 numbers with a maximum of 20 and the "high" heap contains 10 numbers with a minimum of 25. Assume the next input is 15. Which of the following statements will be guaranteed to be true after 15 is processed?

 The maximum of the low heap will be 15
 The maximum of the low heap will be 25
 The minimum of the high heap will be 15
 The minimum of the high heap will be 20
 
 Why is the last answer correct?

ceejay562
Posts: 25
Posted 18:32 Dec 08, 2014 |
The min of the high heap is 25 and the max of the low heap is 20. Low heap is size 11 and max heap is size 10. The max and low heap can only differ by one. So you want to insert an integer less than the largest value in the low heap 15 <20. So you insert 20 into the high heap and 15 into the low heap. So 20 is how thr smallest integer in the high heap
G190852562
Posts: 162
Posted 19:48 Dec 08, 2014 |
ceejay562 wrote:
The min of the high heap is 25 and the max of the low heap is 20. Low heap is size 11 and max heap is size 10. The max and low heap can only differ by one. So you want to insert an integer less than the largest value in the low heap 15 <20. So you insert 20 into the high heap and 15 into the low heap. So 20 is how thr smallest integer in the high heap

Why do we have to insert 20 into the high heap? Aren't we only dealing with 15 here? Is it because the 20 gets pushed over to the high heap after inserting 15 (making it the new minimum)?

Last edited by G190852562 at 19:49 Dec 08, 2014.
vsluong4
Posts: 87
Posted 20:36 Dec 08, 2014 |

Yes, that is exactly right.

 

This is how the two heaps stay balanced.  After inserting 15 into one of the heaps, one of the heaps has size 10 and the other 12.  Now let's say we add the numbers -1 to -100 without any sort of rebalancing.  After adding -100, one heap will still number 10 and the other 112!  Obviously it's going to be fruitless trying to get the median of the numbers using those heaps.  Balancing involves removing an element from the larger heap and adding to the smaller one when their size differences is 2.