打印N个数组整体最大的TopK

题目:

　　有N个长度不一的数组，所有的数组都是有序的，请从大到小打印这个N个数组整体最大的前K个数。 
　　例如，输入含有N行元素的二维数组可以代表N个一维数组。 
　　219, 405, 538, 845, 971 
　　148, 558 
　　52, 99, 348, 691 
　　再输入整数k = 5，则打印： 
　　971, 845, 691, 558, 538

要求:

如果所有数组的元素个数小于K，则从大到小打印所有的数
要求时间复杂度为O(KlogN)

基本思路:

　　本题的解法是利用堆结构和堆排序的过程完成的，具体过程如下：

构建一个大小为N的大根堆，建堆的过程就是把每一个数组的最后一个值，也就是该数组的最大值，依次加入到堆里，这个过程就是建堆的调整过程。

建好堆以后，此时堆顶的元素就是所有数组中最大的元素，打印堆顶元素。

假设堆顶的元素来自 a 数组的 i 位置，那么将堆顶的元素用a[i-1]替换，然后从堆的头部重新调整堆。如果发现此时 a 数组已经没有元素，那么就将堆顶元素与堆尾元素交换，同时令堆的大小减1，仍然是从堆的头部重新调整堆。

每次都可得到一个堆顶元素，打印k个堆顶元素，就是最终的结果。
 

class Heap:def __init__(self,value,arrNum,index):self.value = valueself.arrNum = arrNumself.index = indexdef printTopk(matrix,k):if matrix == None or len(matrix) == 0:return NoneheapSize = len(matrix)heap = [0 for i in range(heapSize)]for i in range(len(heap)):heap[i] = Heap(matrix[i][index],i,len(heap[i])-1)heapInsert(heap,i)print("Tok " + str(k) + " : ")for i in range(k):if heapSize == 0:breakprint(heap[0].value + " ")if heap[0].index!=0:heap[0].value = matrix[heap[0].arrNum][heap[0].index-1]heap[0].index -=1else:heap[0] = heap[-1]heapSize -= 1heapify(heap,0,heapSize)def heapInsert(heap,index):while parent!=0:parent = int((index-1)/2)if heap[index].value > heap[parent].value:swap(heap,index,parent)index = parentelse:breakdef heapify(heap,index,heapSize):left = 2 * index +1right = 2 * index + 2largest = indexwhile left < heapSize:if heap[left].value > heap[largest].value:largest = leftif right < heapSize and heap[right].value > heap[largest].value:largest = rightif largest != index:swap(heap,largest,index)else:breakindex = largestleft = 2 * index + 1right = 2 * index + 2def swap(heap,index1,index2):tmp = heap[index1]heap[index1] = heap[index2]heap[index2] = tmp

 

总结

以上是生活随笔为你收集整理的打印N个数组整体最大的TopK的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。