用最小堆找第k个数

用最小堆找第k个数，包含了堆的构建代码和寻找代码，但是效率比较低下，只能用于小规模数据
建堆转自https://www.cnblogs.com/IronDukeLinux/p/10728513.html

def sift(self,li,low,high):  # low是根节点所在位置的下标，high是要调整的树的最后一个元素的下标（用于判断是否结束调整）
    tmp = li[low]  # 根节点的值存起来
    i = low  # 根节点下标
    j = 2 * i + 1  # 根节点左孩子下标
    while j <= high:  # 判断j是否存在，不存在说明可以结束调整了
        if j + 1 <= high and li[j+1] > li[j]:  # 如果右孩子存在并且比左孩子大
            j += 1  # j指向右孩子
        if li[j] > tmp:  # 如果孩子的值比父亲的大，需要进行调整，否则可以结束调整
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:
            break
    li[i] = tmp  # 调整结束，将tmp的值放到调整后的位置
def heap_sort(self,li):
    # 1. 建堆
    n = len(li)
    for i in range(n//2-1, -1, -1):# i表示遍历的low, n//2-1是最后一个非叶子节点的下标
        self.sift(li, i, n-1)
def findKthLargest(self, nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: int
    """
    list1 = []#构建一个堆数组
    for i in range(len(nums)):
        list1.append(-nums[i])
        self.heap_sort(list1)#向堆中添加元素后排序
        if len(list1)>k:#如果堆中元素大于k，则将首元素取出，并将尾元素放到队首，重新排序
            temp = list1.pop()
            list1[0] = temp
            self.heap_sort(list1)
    return -list1[0]#输出队首元素即为所求

最后

以上就是陶醉宝马为你收集整理的用最小堆找第k个数的全部内容，希望文章能够帮你解决用最小堆找第k个数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。