首先，堆队列a，b排序（升序），各需nlogn
第二步：a[1]+b[1],a[1]+b[2],,,a[1]+a[n]的值插入堆中作为初始最大堆,需nlogn
第三步:a[2]+b[x]..x从1开始一直到a[2]+b[x]>最大堆的堆顶，小于最大堆的堆顶则删除堆顶，插入这个值，这一步最多进行n/2 次（
原因就是因为a[1]<a[2]，如果a[2]能和b数组组合得到最小值，那么a[1] 和b数组组合会得到更多的最小值，所有如果a[2]+b[x]最多只能替换堆顶n/2次
）
第四步：a[3]+b[x]..]..x从1开始一直到a[2]+b[x]>最大堆的堆顶，这一步最多进行n/4 次
(原因同上)
第四步：a[4]+b[x]..]..x从1开始一直到a[2]+b[x]>最大堆的堆顶，这一步最多进行n/8 次
(原因同上)
故用时n/2+n/4+n/8+....=(n/2)/(1/2)=n 再乘以每次删除堆顶在插入堆的logn,故总共需要nlogn次
详见http://blog.sina.com.cn/s/blog_5ceeb9ea0100ku7g.html

• Re:可用堆O(nlgn)的时间取得2个队列和的最小n个元素的原因 (597) leonardWang 2013-02-16 19:53:08