leetcode-703-Kth-Largest-Element-in-a-Stream

1. 题目

设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。

示例:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3); // returns 4
kthLargest.add(5); // returns 5
kthLargest.add(10); // returns 5
kthLargest.add(9); // returns 8
kthLargest.add(4); // returns 8
说明:
你可以假设 nums 的长度≥ k-1 且k ≥ 1。

2. 解

优先队列，即堆

class KthLargest(object):

    def __init__(self, k, nums):
        """
        :type k: int
        :type nums: List[int]
        """
        self.k = k
        self.nums = nums
		
		# 将nums(list)就地转换为heap对象
        heapq.heapify(self.nums)
		
		# 如果nums长度大于k，则只保留K个结点的堆，根节点就是第K个大的值
        while len(self.nums) > self.k:
            heapq.heappop(self.nums)
        
    def add(self, val):
        """
        :type val: int
        :rtype: int
        """
		
		# 如果nums长度小于k，则将val压入堆中
        if self.k > len(self.nums):
            heapq.heappush(self.nums,val)
		
		# 否则nums长度大于k时，先将val压入堆，排序好之后，pop根节点
        else:
            heapq.heappushpop(self.nums,val)
        return self.nums[0]
            
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)

这里用到了堆数据结构（Heap）

# 将已知的 list 转化为 heap 对象，默认为小顶堆
heapq.heapify(list)

# 将 item 压入 heap
heapq.heappush(heap,item)

# 弹出 heap 中最小的值，即为树的根节点
heapq.heappop(heap)

# 将 item 压入 heap，弹出最小值，并重新排序堆结构
heapq.heappushpop(item)