堆
堆（Heap）是一种树状数据结构，它是一种特殊的完全二叉树，满足堆的性质：对于每个节点x，它的父节点的值都比x的值要大（或者小）。
通常情况下，我们所说的堆一般指的是二叉堆，即只有二个子节点的堆。二叉堆分为两种：最大堆和最小堆。在最大堆中，每个节点的值都大于等于其子节点的值，根节点是最大值；在最小堆中，每个节点的值都小于等于其子节点的值，根节点是最小值。
堆常被用来实现优先队列（Priority Queue），堆排序（Heap Sort）等算法。堆可以在O(log n)的时间复杂度内进行插入和删除操作，并且可以在O(1)的时间复杂度内找到最大或最小值，因此在一些需要快速找到最大或最小值的算法中，堆非常有用。
应用场景
堆（Heap）可以应用于很多场景，其中一些典型的应用场景包括：
- 实现优先队列：在优先队列中，每个元素都有一个优先级，堆可以非常高效地实现优先队列的插入、删除和查找最大/最小元素的操作。
- 堆排序：堆排序是一种高效的排序算法，它利用堆的特性来实现排序。堆排序的时间复杂度为O(nlogn)，而且可以原地排序（不需要额外的存储空间）。
- 求Top K问题：在一个数据集中找出前K个最大/最小的元素，堆可以用来维护前K个最大/最小元素。
- 求中位数：对于一个数据流，堆可以用来维护其中位数。
- 哈夫曼编码：哈夫曼编码是一种可变字长编码，它利用堆来实现最优编码。
- Dijkstra算法：Dijkstra算法是一种用于计算最短路径的算法，它可以利用堆来实现优化，减少计算时间。
除了以上这些典型的应用场景之外，堆还可以用于图论、搜索算法、贪心算法等领域的一些算法中。总之，堆是一种非常有用的数据结构，可以在很多场景中提高算法的效率和性能。
最大堆
最大堆（Max Heap）是一种满足堆性质的二叉树结构，其中任意一个节点的值都大于等于其左右子节点的值。即，如果节点A是节点B的父节点，那么节点A的值一定大于等于节点B的值。在最大堆中，根节点的值是整个堆中的最大值。
最大堆通常用来实现优先队列（Priority Queue），其中每个元素都有一个优先级，而优先级高的元素被优先处理。在最大堆中，根节点的优先级最高，因此可以被优先处理。
最大堆可以用数组来实现，具体方法是按照从上到下、从左到右的顺序依次将元素存放在数组中。对于任意一个节点i，它的左子节点的索引是2i+1，右子节点的索引是2i+2，而它的父节点的索引是(i-1)/2。这样，我们就可以用数组来实现最大堆的插入和删除操作了。
最大堆的时间复杂度为O(logn)，其中n是堆的大小。插入和删除操作都需要维护堆的性质，因此时间复杂度是O(logn)的。查找最大值的时间复杂度是O(1)，因为最大值是根节点。
最小堆
最小堆（Min Heap）是一种满足堆性质的二叉树结构，其中任意一个节点的值都小于等于其左右子节点的值。即，如果节点A是节点B的父节点，那么节点A的值一定小于等于节点B的值。在最小堆中，根节点的值是整个堆中的最小值。
最小堆通常用来实现优先队列（Priority Queue），其中每个元素都有一个优先级，而优先级低的元素被优先处理。在最小堆中，根节点的优先级最低，因此可以被优先处理。
最小堆可以用数组来实现，具体方法与最大堆类似，只是在插入和删除操作时需要维护堆的性质。对于任意一个节点i，它的左子节点的索引是2i+1，右子节点的索引是2i+2，而它的父节点的索引是(i-1)/2。这样，我们就可以用数组来实现最小堆的插入和删除操作了。
最小堆的时间复杂度为O(logn)，其中n是堆的大小。插入和删除操作都需要维护堆的性质，因此时间复杂度是O(logn)的。查找最小值的时间复杂度是O(1)，因为最小值是根节点。