由概率论中的顺序统计量得到的小顶堆求第k个元素的方法

今天概率论老师讲了数理统计部分,里面有个顺序统计量,定义是:

$$X_k^{\ast }=max\left\{min\{X_{i_1},X_{i_2},...,X_{i_{n-k+1}}\}\right\},k=1,2,...,n$$
(没想到html还能内嵌)

当时我就灵机一闪,这不是用堆求kth个数的问题吗!而且一般求第k大的数都是基于大顶## 堆,按照书上这个定义不就可以用小顶堆求kth问题了吗,果然世界的本质就是数学,话不多说,用py实现一下:

import heapq

def kth_largest_maxheap(nums, k):
    #默认为小顶堆,转变为大顶堆
    max_heap = []
    for num in nums:
        # 将当前元素相反数加入堆,转变为大顶堆
        heapq.heappush(max_heap, -num)
        # 如果堆的大小超过 k，移除堆顶元素
        if len(max_heap) > k:
            heapq.heappop(max_heap)
    
    # 堆顶元素就是第 k 大的元素,加负号恢复值
    return -max_heap[0]

def kth_largest_minheap(nums, k):
    #默认为小顶堆
    min_heap = []
    min_list = []
    for num in nums:
        heapq.heappush(min_heap, num)
        # 取出n-k+1个体中的最小值
        if len(min_heap) > len(nums)-k:
            min_list.append(heapq.heappop(min_heap))
    print(min_list)
    return max(min_list)

drive code

if __name__ == '__main__':
    nums = [3, 7, 1, 9, 6, 4, ]

    k = 4

    print(kth_largest_maxheap(nums, k))
    print(kth_largest_minheap(nums, k))

结果输出符合预期:)