/* 小根堆 */

typedef struct {

    int heapCapacity;

    int heapSize;

    int *heap;

} KthLargest;

/* 堆顶下标: 0; parent: (k-1)/2; leftChild: 2*k + 1; rightChild: 2*k + 2 */

int ParentIndex(int i)

{

    return (i - 1) / 2;

}

int LeftChildIndex(int i)

{

    return 2 * i + 1;

}

int RightChildIndex(int i)

{

    return 2 * i + 2;

}

void Swap(int *a, int *b)

{

    int tmp = *a;

    *a = *b;

    *b = tmp;

}

/************************************ 堆的有序性的维护 ************************************/

/*

* 上浮：

*     不符合规则的点（这里是小根堆，规则即父节点最小），与父节点交换（直至符合为止）

*/

void Swim(int *heap, int i)

{

    while (i > 0 && heap[ParentIndex(i)] > heap[i]) {

        Swap(&heap[ParentIndex(i)], &heap[i]);

        i = ParentIndex(i); // 已经上浮一次，更新下次可能上浮的索引

    }

}

/*

* 下沉：

*     不符合规则的点（这里是小根堆，规则即父节点最小），与子节点中较小的（因为是小根堆）交换（直至符合为止）

*/

void Sink(int *heap, int heapSize, int i)

{

    while (LeftChildIndex(i) < heapSize) {

        int smallOneIndex = LeftChildIndex(i);

        int leftVal = heap[LeftChildIndex(i)];

        if (RightChildIndex(i) < heapSize) {

            int rightVal = heap[RightChildIndex(i)];

            // 比较子节点中哪个更小

            smallOneIndex = leftVal < rightVal ? smallOneIndex : RightChildIndex(i);

        }

        if (heap[i] < heap[smallOneIndex]) {

            break;

        }

        Swap(&heap[i], &heap[smallOneIndex]);

        i = smallOneIndex; // 已经下沉一次，更新下次可能上浮的索引

    }

}

/*

* 出队：

*     1.最后一个点换到根（根即待出队的点）

*     2.下沉

*/

void Pop(int *heap, int *heapSize)

{

    Swap(&heap[0], &heap[*heapSize - 1]);

    // heap[*heapSize - 1] = 0;

    (*heapSize)--;

    Sink(heap, *heapSize, 0);

}

/*

* 入队：

*     1.待插入的点放在最后

*     2.上浮

*/

void Push(int *heap, int *heapSize, int val)

{

    heap[(*heapSize)++] = val;

    Swim(heap, *heapSize - 1);

}

/************************************ 答题 ************************************/

int kthLargestAdd(KthLargest* obj, int val)

{

    if (obj->heapCapacity > obj->heapSize) {

        Push(obj->heap, &obj->heapSize, val);

    } else if (val > obj->heap[0]) {

        // 队列已经满了，并且头节点小于待插入的值

        Pop(obj->heap, &obj->heapSize);

        Push(obj->heap, &obj->heapSize, val);

    }

    // 小根堆，每次返回头节点

    return obj->heap[0];

}

KthLargest* kthLargestCreate(int k, int* nums, int numsSize)

{

    if (k < 1) {

        return NULL;

    }

    KthLargest *obj = (KthLargest *)malloc(sizeof(KthLargest));

    obj->heapCapacity = k;

    obj->heapSize = 0;

    obj->heap = (int *)malloc(sizeof(int) * k);

    memset(obj->heap, 0, sizeof(int) * k);

    for (int i = 0; i < numsSize; i++) {

        if (obj->heapCapacity > obj->heapSize) {

            Push(obj->heap, &obj->heapSize, nums[i]);

        } else {

            // 堆已经满了，调用add接口

            int ret = kthLargestAdd(obj, nums[i]);

        }

    }

    return obj;

}

void kthLargestFree(KthLargest* obj)

{

    if (obj != NULL) {

        free(obj->heap);

        free(obj);

    }

}

/**

 * Your KthLargest struct will be instantiated and called as such:

 * KthLargest* obj = kthLargestCreate(k, nums, numsSize);

 * int param_1 = kthLargestAdd(obj, val);

 * kthLargestFree(obj);

*/

struct hashTable {

    int key;    // 数组元素

    int value;  // 数组元素出现的频率

    UT_hash_handle hh;

};

struct hashTable *g_hash;

void AddNode(int num)

{

  struct hashTable *tmp = NULL;

  HASH_FIND_INT(g_hash, &num, tmp);

  if (tmp == NULL) {

      tmp = (struct hashTable *)malloc(sizeof(struct hashTable));

      tmp->key = num;

      tmp->value = 1;

      HASH_ADD_INT(g_hash, key, tmp);

  } else {

      (tmp->value)++;

  }

}

/* 排序：逆序 */

int HashCmp(struct hashTable *a, struct hashTable *b)

{

    return b->value - a->value;

}

/**

 * Note: The returned array must be malloced, assume caller calls free().

 */

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize)

{

    g_hash = NULL;

    for (int i = 0; i < numsSize; i++) {

        // 插入到hash表中

        AddNode(nums[i]);

    }

    // 根据数组元素出现的频次，对hash表进行降序

    HASH_SORT(g_hash, HashCmp);

    int *res = (int *)malloc(sizeof(int) * k);

    *returnSize = k;

    int cnt = 0;

    // 对hash表进行遍历

    struct hashTable *cur, *tmp;

    HASH_ITER(hh, g_hash, cur, tmp) {

        if (cnt == k) {

            break;

        }

        res[cnt++] = cur->key;

    }

    return res;

}