TopK问题介绍：
TOP-K问题：即求数据中找出前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
在N个数中找出最大/小的前K个 （比如在1000个数中找出最大/小的前10个）
以前的方法：冒泡排序。时间复杂度： O(N^2)
现在找最大的k个数的方法：
方法1：堆排序降序，前N个就是最大的。上篇学过时间复杂度： O(N*logN)
方法2：N个数依次插入大堆，HeapPop K次，每次取堆顶的数据，即为前K个。
时间复杂度： O(K*logN)
假设 N非常大， 是 10 亿，内存中存不下这些数，它们存在文件中的。 K是 100，
上面的方法就都不能用了……
话说 10 亿个整数，大概占用多少空间？
1G = 1024MB
1G = 1024*1024KB1G = 1024*1024*1024Byte要占用10亿字节！所以我们来看看方法3：
方法3： 
这里为什么使用小堆而不使用大堆？
后N-k个数，比小堆堆顶大就换成堆顶
（最后堆顶就是最大的k个数中最小的）
最大的前K个数一定会比其他数要大，只要进来的数比堆顶数据大，就替代它。
因为是小堆（小的在上大的在下），最大的数进去后一定会沉到下面，
所以不可能存在大的数堵在堆顶导致某个数进不去的情况，数越大沉得越深。
对应地，如果使用大堆就会出现一个大数堵在堆顶，剩下的数都比这个大数小，
导致其他数进不来，最后只能选出最大的那一个。
（以下两个力扣题可以用其它排序解决（比如C++中自带的更优的快排）
不过是看你是面向offer还是面向竞赛或刷题了。
（以后学了八大排序可以自己实现一下对应题目优化的快排）以下我们使用堆来解决
剑指 Offer 40. 最小的k个数
难度简单
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，
则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
限制：
- 0 <= k <= arr.length <= 10000
- 0 <= arr[i] <= 10000
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){ }
解析代码：
（这里是找最小的k个数，所以建k个数的大堆）后arrSize-k个数，比大堆堆顶小就换成堆顶
（最后堆顶就是最小的k个数中最大的）
/** * Note: The returned array must be malloced, assume caller calls free(). */ void justDown(int* arr, int n, int root)//大堆下调 { int father = root; int child = father * 2 + 1;//默认左孩子大 while (child < n) { if (child + 1 < n && arr[child] < arr[child + 1]) { // 如果右孩子存在且右孩子比左孩子大 child++; } if (arr[father] < arr[child]) { int tmp = arr[father]; arr[father] = arr[child]; arr[child] = tmp; father = child; child = father * 2 + 1; } else { break; } } } int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize) { *returnSize = k; if (k == 0)//回头处理k==0 { return NULL; } int* retArr = (int*)malloc(sizeof(int) * k); for (int i = 0;i < k;i++) { retArr[i] = arr[i]; } for (int i = (k - 1 - 1) / 2;i >= 0;i--) //建堆的for写法 { justDown(retArr, k, i); } for (int j = k;j < arrSize;j++)//后arrSize-k个数，比大堆堆顶小就换成堆顶 { if (arr[j] < retArr[0]) { retArr[0] = arr[j]; justDown(retArr, k, 0);//把新换的堆顶向下调整（小的就下去了），以便下次交换 } } //*returnSize = k; 写到这发现有个测试用例跑不了，到上面处理一下 return retArr; }
剑指 Offer II 076. 数组中的第 k 大的数字
难度中等
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入:[3,2,1,5,6,4] 和 k = 2 输出: 5
示例 2:
1. 输入:[3,2,3,1,2,4,5,5,6] 和 k = 4 2. 输出: 4
提示：
- 1 <= k <= nums.length <= 10^4
- -10^4 <= nums[i] <= 10^4
int findKthLargest(int* nums, int numsSize, int k){ }
解析代码：
这里我们需要把整个数组建成一个大堆，然后pop（k-1）次堆顶的元素后堆顶的元素就是第k大的数。
void Swap(int* px, int* py) { int tmp = *px; *px = *py; *py = tmp; } void justDown(int* arr, int n, int root)//大堆下调 { int father = root; int child = father * 2 + 1;//默认左孩子大 while (child < n) { if (child + 1 < n && arr[child] < arr[child + 1]) { // 如果右孩子存在且右孩子比左孩子大 child++; } if (arr[father] < arr[child]) { Swap(&arr[father], &arr[child]); father = child; child = father * 2 + 1; } else { break; } } } int findKthLargest(int* nums, int numsSize, int k) { for (int i = (numsSize - 1 - 1) / 2;i >= 0;i--) //建堆的for写法 { justDown(nums, numsSize, i); } // 删除数据（参考前面文章堆的pop） for (int i = 1;i <= k - 1;i++) { Swap(&nums[0], &nums[numsSize - i]); justDown(nums, numsSize - i, 0);//删除多少个numsize-多少个 } return nums[0]; }
堆的概念选择题：
1.下列关于堆的叙述错误的是（ ）
A.堆是一种完全二叉树
B.堆通常使用顺序表存储
C.小堆指的是左右孩子结点都比根结点小的堆
D.堆的删除是将尾部结点放到队顶后执行向下调整算法
2.下列关键字序列中，序列（ ）是堆。
A.{16，72，31，23，94，53}
B.{94，23，31，72，16，53}
C.{16，53，23，94，31，72}
D.{16，23，53，31，94，72}
3.下列关于向下调整算法的说法正确的是（ ）
A.构建堆的时候要对每个结点都执行一次
B.删除操作时要执行一次
C.插入操作时要执行一次
D.以上说法都不正确
4.在一个堆中，根节点从0开始编号，下标为 i（i > 0） 的结点的左右孩子结点及父结点的下标分别是（ ）
A.2 i、2 i + 1、i /2
B.2i、2i + 1、(i - 1)/2
C.2i + 1、2i + 2、(i - 1)/2
D.2i + 1、2i + 2、i/2-1
5.将一个顺序表利用向下调整的方式整理成堆的时间复杂度为（ ）
A.O(nlogn)
B.O(logn)
C.O(1)
D.O(n)
答案：
1.答案：C
堆是在完全二叉树的基础上进行了条件的限制，即：每个节点都比其孩子节点大，则为大堆；
每个节点都比其孩子节点小则为小堆。
完全二叉树比较适合使用顺序结构存储。
堆删除：删的是堆顶元素，常见操作是将堆顶元素与堆中最后一个元素交换，
然后对中元素个数减少一个，重新将堆顶元素往下调整
2.答案：D
D.{16，23，53，31，94，72}
16
23 53
31 94 72
3.答案：B
解析：
A: 建堆时，从每一个非叶子节点开始，倒着一直到根节点，都要执行一次向下调整算法。
B: 删除元素时，首先交换堆顶元素与堆中最后一个元素，对中有效元素个数减1，即删除了堆中最后一个元素，最后将堆顶元素向下调整
C: 插入操作需要执行向上调整算法。
4.答案：C
请参考二叉树性质
5.答案：D
题目说了是利用向下调整的方式建堆， 正确的证明方法应当如下：
A.具有n个元素的平衡二叉树，树高为㏒n，我们设这个变量为h。
B.最下层非叶节点的元素，只需做一次线性运算便可以确定大根，而这一层具有2^(h-1)个元素，
我们假定O(1)=1，那么这一层元素所需时间为2^(h-1) × 1。
C.由于是bottom-top建立堆，因此在调整上层元素的时候，并不需要同下层所有元素做比较，只需要同其中之一分支作比较，而作比较次数则是树的高度减去当前节点的高度。因此，第x层元素的计算量为2^(x) × (h-x)。
D.又以上通项公式可得知，构造树高为h的二叉堆的精确时间复杂度为：
S = 2^(h-1) × 1 + 2^(h-2) × 2 + …… +1 × (h-1) ①
E.通过观察第四步得出的公式可知，该求和公式为等差数列和等比数列的乘积，因此用错位相减法求解，给公式左右两侧同时乘以2，可知：
2S = 2^h × 1 + 2^(h-1) × 2+ …… +2 × (h-1) ②
用②减去①可知： S =2^h × 1 - h +1 ③
将h = ㏒n 带入③，得出如下结论：
S = n - ㏒n +1 = O(n)
