问题描述:现有n个有序序列如(2,3,9),(3,5,11,23),(1,4,7,9,15,17,20),(8,15,35,9),(20,30,40),请求出第k小值。
问题分析:可用多路归并排序将所有序列进行排序后取第k个值,但是只要求求出第k小值将所有数组排序未免显得有点浪费,所以我们可以使用包含k个元素的堆完成,对于每组元素取出前k小的,依次进行比较,得到总的前k小
执行步骤:
一、建初堆:从第一组数中取出前k小的元素建初始大根堆(若不足k个则取全部元素),
二、
1 、补充堆:若堆中元素不足k个,则从下一组数中获取来补足
2、与该组元......
阅读全文