堆总结（C语言）二叉树的顺序结构及实现
堆是什么
堆总是一棵完全二叉树，堆是用来存完全二叉树的，如果存普通的二叉树就会浪费空间。堆(一种二叉树)使用顺序结构的数组来存储。堆不是简单的存储数据，还有些功能，堆可以筛选数据（删堆顶元素）时间复杂度是O(logN)，堆排序。
堆的分类
- 大堆：父节点的值大于等于子节点。
- 小堆：父节点的值小于等于子节点。
堆的实现
堆的向下调整
- 前提条件：左子树和右子树是堆。
- 常应用：删除堆顶数据可以堆排序（堆顶是最大（小）的，删数据时，不是将数据整体向前挪动一位，因为这样会效率低下，而且父子兄弟关系混乱，又要重新实现堆，时间复杂度大,是O(N)或O(N*logN)，有个牛B的方法就是将首数据与尾数据交换，再Pop最后的数据，再向下调整，这个时间复杂度是O(logN)），建堆，时间复杂度是O(N),向上调整也可以建堆，但是它的时间复杂度是O(N *LogN)。
可以这样记：二叉树的最后一层大约占一半2^(h-1)，倒数第二层的节点大约占1/4，向下调整建堆是节点数量多的层遍历的深度小，上面节点少的层遍历深度大；向上建堆是上面节点少的层遍历深度小，下面节点多的层遍历深度大。
堆的向上调整
- 前提条件:在插入一个数据之前，是堆。
- 常应用：向堆插入数据
堆的应用
堆排序
两个步骤：
-
建堆
升序：建大堆，因为堆顶元素与尾元素互换，最大的放在最后，次大的放在倒二。 降序：建小堆
2.利用堆思想来进行排序
建堆和堆删除中都用到了向下调整，用向下调整就可以完成堆排序。
TOP-K问题
TOP-K问题：在大量的数据中，求前 K 个最大元素或最小元素。
思路:
1.在数据的前k个元素来建堆
2.剩下的N-K个元素依次与堆顶元素进行比较
