20180723剑指offer题30——最小的k个数

一、要求

    举个例子：

输入：[4,5,1,6,2,7,3,8]

输出：1，2，3  不要求顺序

 

二、思路及代码

当数据较少时，有很多方法可以实现，min啊，排序啊，堆的nsmallest函数啊

当数据较多时，考虑到内存，用一个堆实现，python自带最小堆库heapq，对输入数据取负可变成最大堆，处理成最大堆的意义在于调整堆顶元素时比较方便。

最小堆：所有父节点的值都比子节点要小

heapq库：有取n个最小值函数heap.nsmallest(n,list)   ;入堆函数heap.heappush（self.data，elem）；堆数据调整函数 heap.replace(self.data,elem)   ;堆顶元素为self.data[0]

import heapq

class Maxheapq():
    def __init__(self,k):
        self.n=k
        self.data=[]
    def push(self,elem):
        if len(self.data)<self.n:
            heapq.heappush(self.data,-elem)#将heapq的最小堆转化为最大堆
        else:
            if elem<-self.data[0]:
                heapq.heapreplace(self.data,-elem)
    def Ksmallest(self):
        return [-i for i in self.data]




a=[4,5,1,6,2,7,3,8]
print(heapq.nsmallest(3,a))
b=Maxheapq(3)
b.push(4)
b.push(5)
b.push(1)
b.push(6)
b.push(2)
b.push(7)
b.push(3)
b.push(8)
print(b.Ksmallest())

 

 

三、运行结果

[1, 2, 3]
[3, 2, 1]

 

四、思考与总结

对[4,5,1,6,2,7,3,8]找最小的7个数，结果是[7, 5, 6, 4, 2, 1, 3]

堆中的数据疑似是以层遍历存储在[]里的