topK问题

（1）时间复杂度分析：
每次调用'self.heapAdjust(self.arr, n, i)'的时间复杂度是O（lgn）（只需要走完树的深度h的时间次数），需要调用O（n）次，总的时间是O（nlgn）
（2）树的深度求解（边的数目==结点数目-1，结点都唯一的跟它上面的一条边链接）：
二叉树的从上往下，1棵变2棵，2棵子树变成4棵树，4又变8.。。，即：(有多少项，树的高度就是多少)，由等比数列有：得（即树的高度跟是线性关系）

"""
topk问题思想：假设是返回数组中最大的k个数。
（1）借助于堆排序的思想，用一个长度为k的数字arr去维护
最大的k个数，len(arr)<k的时候，直接插入.
（2）当len(arr)==k的时候，这个时候需要建立堆，
然后堆顶的元素在插入时候需要跟新元素e比较的(采用堆顶比较只需要从root
往下调整一次就好)，如果e大于堆顶元素，那么堆顶元素被替换为e，然后需要
从root往下调整一次。
"""
class Solution:
    def __init__(self,capacity):
        self.arr = []
        self.capacity = capacity

    def insert(self,e):
        if len(self.arr)<self.capacity:
            self.arr.append(e)
            return
        #建立堆的过程
        n = len(self.arr)
        #int(n/2-1)保证了非叶子结点，n是最大的index+1
        for i in range(int(n/2-1),-1,-1):
            self.heapAdjust(self.arr, n, i)
        #调整堆的过程
        if e>self.arr[0]:
            self.arr[0] = e
            self.heapAdjust(self.arr,n,0)

    def heapAdjust(self,arr,n,i):
        minest = i
        left = i*2+1
        right = i*2+2
        if left<n and arr[left]<arr[minest]:
            minest = left
        if right<n and arr[right]<arr[minest]:
            minest = right
        if i!=minest:
            arr[i],arr[minest] = arr[minest],arr[i]
            self.heapAdjust(arr,n,minest)


if __name__ == "__main__":
    k = 3
    nums=[1,3,6,5,9,8,11,20]
    so = Solution(k)
    for e in nums:
        so.insert(e)
        print(so.arr)