简介
概念
堆是一种比拟非凡的数据结构，它用数组实现的二叉树，并且总是满足以下性质：
- 堆总是一棵齐全二叉树
- 堆中某个结点总是不大于或不小于其父结点的的值
属性
堆分为两种：根结点最大的堆叫作 最大堆 或大根堆 ；根结点最小的堆叫作 最小堆 或小根堆。
堆属性十分有用，其使得堆经常被当做优先队列应用，因为能够疾速地拜访到“最重要”的元素。
堆和二叉搜寻树的区别
堆并不能取代二叉搜寻树，它们之间有相似之处也有一些不同。两者的次要区别如下：
| 属性 | 堆 | 二叉搜寻树 |
|---|---|---|
| 结点的程序 | 在最小堆中父结点必须比子结点小，在最大堆中父结点必须比子结点大，变动是从上到下 | 左子结点比父结点小，父结点比右子结点小，变动是从左到右 |
| 内存占用 | 应用数组作为底层存储构造，占用内存空间较小 | 应用链表作为底层存储构造，占用内存空间较大 |
| 均衡 | 不须要整棵树有序 | 必须是均衡的，总体上是有序的 |
| 搜寻 | 搜寻很慢 | 搜寻很快 |
堆的实现
存储
实现一个堆，首先是波及到如何存储一个堆。
依据堆总是一棵齐全二叉树的性质，以及齐全二叉树比拟适宜用数组来存储的概念，能够晓得用数组存储堆是比拟好的抉择。
从上图能够看到，数组中下标为 i 的结点的左子结点，就是下标为 2i 的结点，右子结点就是下标为 2i + 1 的结点，父结点就是下标为 i/2 的结点。
堆化
往堆中插入或者删除一个元素后，重要的是须要持续满足堆的两个个性，而这个从新满足堆个性的过程称为 堆化。
堆化实际上有两种：从下往上、从上往下。
插入元素
插入元素时波及的是从下往上的堆化办法。
往堆中插入一个元素其实就是往底层数组的开端增加元素，上面是示例图：
从下往上堆化的过程比较简单，实际上就是将插入的元素与父结点进行比拟，呈现不合乎个性的状况就调换两个结点，始终反复这个过程，直至父子结点之间满足堆的个性。
删除元素
从堆的个性能够看出，堆顶元素存储的就是堆中数据的最大值或最小值。
当删除堆顶元素的时候，为放弃堆的个性，则会波及到从上往下的堆化办法。
从上往下堆化不是间接从堆顶元素开始与子结点进行调换，而是先将数组中的最初一个元素移到被删除结点地位（为了满足齐全二叉树的个性），而后利用同样的父子结点比对办法。
通常，对于大根堆会比拟较大的子结点，对于小根堆会比拟较小的子结点，呈现不合乎个性的状况就调换两个结点，始终反复这个过程，直至父子结点之间满足堆的个性。
这种办法堆化之后的后果，必定满足齐全二叉树的个性。
复杂度
一个蕴含 n 个节点的齐全二叉树，树的高度不会超过 $\log_2n$。
堆化的过程是顺着节点所在门路比拟替换的，所以堆化的工夫复杂度跟树的高度成正比，也就是 $O(\log n)$。
插入数据和删除堆顶元素的次要逻辑就是堆化，所以往堆中插入一个元素和删除堆顶元素的工夫复杂度都是 $O(\log n)$。