一.概念及其介绍

1.堆(Heap)是计算机科学中一类特殊的数据结构的统称。

堆就是以二叉树的顺序存储方式来存储元素，同时又要满足父亲结点存储数据都要大于等于儿子结点存储数据（也可以是父亲结点数据都要小于等于儿子结点数据）的一种数据结构。

堆只有两种即大堆和小堆，大堆就是父亲结点数据大于等于儿子结点数据，小堆则反之。

2.堆满足下列性质：

堆中某个节点的值总是不大于或不小于其父节点的值。

堆总是一棵完全二叉树。

二.适用说明

堆是利用完全二叉树的结构来维护一组数据，然后进行相关操作，一般的操作进行一次的时间复杂度在 O(1)~O(logn) 之间，堆通常用于动态分配和释放程序所使用的对象。

若为优先队列的使用场景，普通数组或者顺序数组，最差情况为 O(n^2)，堆这种数据结构也可以提高入队和出队的效率。

三.堆结构

二叉堆是一颗完全二叉树，且堆中某个节点的值总是不大于其父节点的值，该完全二叉树的深度为 k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边。

其中堆的根节点最大称为最大堆，如下图所示：

四.堆的应用

优先队列实现：用于操作系统任务调度、图算法（如 Dijkstra 算法）等，根据元素优先级处理元素。

堆排序：对数组元素排序，时间复杂度 O (n log n)。

求第 K 大（小）元素：可快速找出第 K 大或第 K 小元素。

中位数维护：使用两个堆维护数据流的中位数。

合并 K 个有序列表：高效合并多个有序列表为一个有序列表。