北京

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

请实现 KthLargest 类：

KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。

int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

示例：

输入：

["KthLargest", "add", "add", "add", "add", "add"]

[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]

输出：

[null, 4, 5, 5, 8, 8]

解释：

KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);

kthLargest.add(3); // return 4

kthLargest.add(5); // return 5

kthLargest.add(10); // return 5

kthLargest.add(9); // return 8

kthLargest.add(4); // return 8

我们首先想到一种暴力的解法，就是首先把输入的数据流进行排序，然后从排好序的数据流中找到第K个元素，就行了，这也是一种解法，我们可以计算一下这种解法情况下的时间复杂度，假设有 N 个元素，要将 K 个元素进行快速排序，那么时间复杂度就为：O ( N ⋅ K ⋅ log ⁡ K ) 。

我们有没有更好的办法来解决这个问题呢？这里我们可以用到优先队列的数据结构（优先队列-二叉堆的运用 ），优先队列的作用是能保证每次取出的元素都是队列中数值最小的，其通过堆实现，通过完全二叉树（complete binary tree）（数据结构：二叉堆 ）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值）。我们可以将优先队列的大小定义成 K ，堆顶就存放的是 K 个元素中最小的那个，当有新的数据流来的时候，就和这个堆顶最小的元素进行比较，比这个堆顶元素小的话，不放进优先队列中；如果新的数据流比堆顶的元素大的话，那么把堆顶的元素剔除，把数据流中的元素加入优先队列。所以说用大小为 K 的优先队列的话，可以保证堆顶一定是第K个大小的元素。这个时候的时间复杂度为： O ( N ⋅ log ⁡ K ) ，所以说用优先队列的方法来解决这个问题是最优的方法。

class KthLargest:    #  小堆优先队列    def __init__(self, k, nums):        self.array = []        self.size = 0        self.kthLargestNum = k        for i in range(len(nums)):            self.add(nums[i])    def enqueue(self, data):        self.array.append(data)        self.size += 1        self.up_adjust()    def dequeue(self):        if self.size < 0:            raise Exception("队列为空！")        ret = self.array[0]        self.array[0] = self.array[self.size - 1]        self.array.pop()        self.size -= 1        self.down_adjust()        #  return ret    def up_adjust(self):        child_index = self.size - 1        parent_index = (child_index - 1) // 2        temp = self.array[child_index]        while child_index > 0 and temp < self.array[parent_index]:            self.array[child_index] = self.array[parent_index]            child_index = parent_index            parent_index = (parent_index - 1) // 2        self.array[child_index] = temp    def down_adjust(self):        parent_index = 0        temp = self.array[parent_index]        child_index = 2 * parent_index + 1        while child_index < self.size:            if child_index + 1 < self.size and self.array[child_index + 1] < self.array[child_index]:                child_index += 1            if temp <= self.array[child_index]:                break            self.array[parent_index] = self.array[child_index]            parent_index = child_index            child_index = 2 * parent_index + 1        self.array[parent_index] = temp    def add(self, val) -> int:        self.enqueue(val)        if(self.size > self.kthLargestNum):            self.dequeue()        return self.array[0]

typedef int ElemType;typedef struct {    ElemType* arr;    int size;    int capacity;    int kthLargestNum;} KthLargest;void Swap(int* a, int* b){    int temp = *a;    *a = *b;    *b = temp;}void checkCapcity(KthLargest* obj){    if(obj->capacity == obj->size)    {        int newCapacity = obj->capacity == 0 ? 1 : 2 * obj->capacity;        obj->arr = (ElemType*)realloc(obj->arr, sizeof(ElemType) * newCapacity);        obj->capacity = newCapacity;    }}void shiftDown(int* arr, int n, int cur){       int child = 2 * cur + 1;    while (child < n)    {        //比较左右子树，找到较小值        if(child + 1 < n && arr[child + 1] < arr[child])        {            ++child;            // child时刻保存较小值的下标        }        if(arr[child] < arr[cur])        {            Swap(&arr[child], &arr[cur]);            cur = child;            child = 2 * cur + 1;        }        else        {            break;        }      } }void shiftUp(int* arr, int n, int cur){    int parent = (cur - 1) / 2;    //假定倒数第一个叶子节点为当前节点cur，找出它的父节点    while (cur > 0)    {//比较父节点和当前节点。当前节点小的话，则不满足小堆规则，需要进行交换        if(arr[cur] < arr[parent])        {            Swap(&arr[cur], &arr[parent]);            cur = parent;            parent = (cur - 1) / 2;        }        else        {            break;        }    }}void heapPush(KthLargest* obj, ElemType val){    checkCapcity(obj);    obj->arr[obj->size++] = val;    shiftUp(obj->arr, obj->size, obj->size -1);}void heapPop(KthLargest* obj){    if(obj->size > 0)    {        Swap(&obj->arr[0], &obj->arr[obj->size - 1]);        obj->size--;        shiftDown(obj->arr, obj->size, 0);    }}ElemType heapTop(KthLargest* obj){    return obj->arr[0];}int kthLargestAdd(KthLargest* obj, int val) {    heapPush(obj, val);    if(obj->size > obj->kthLargestNum)    {        heapPop(obj);    }    return heapTop(obj);}KthLargest* kthLargestCreate(int k, int* nums, int numsSize){    KthLargest* obj = (KthLargest*)malloc(sizeof(KthLargest));    obj->arr = (ElemType*)malloc(sizeof(ElemType));    obj->capacity = obj->size = 0;    obj->kthLargestNum = k;    for (int i = 0; i < numsSize; i++)    {        kthLargestAdd(obj, nums[i]);    }        return obj;}void kthLargestFree(KthLargest* obj) {    free(obj->arr);    obj->arr = NULL;    obj->capacity = obj->size = 0;}

往期精彩：

数据结构：二叉堆

数据结构：二叉堆的自我调整

优先队列-二叉堆的运用

堆排序-二叉堆应用之二