数据结构之堆

一 定义

二叉堆:

1. 完全二叉树
2. 堆中的每个节点(包含的元素值)都大于或等于左、右孩子节点

(注意：层次底的节点的值不一定小于层次高的节点的值。）
最小堆的定义与之类似。

二 底层实现

        逻辑结构是完全二叉树的数据，可以采用顺序存储，即数组实现。
存储结构需要体现逻辑结构，即要能够存储元素（或数据），更重要的是要能存储数据之间的关系。

采用数组作为底层实现后，索引成为了元素的位于标识方式，元素的访问只能通过索引，索引相当于“地址”，于是元素之间的关系也就自然的由索引来体现。

索引是如何体现完全二叉树中各个节点之间的关系呢？

如图所示：我们给逻辑结构完全二叉树中的每一个节点一个编号，即节点在数组中的索引

结点在数组中的存储结构，如下图所示：

观察完全二叉树的逻辑结构，我们可以总结出父亲节点的索引parent和左孩子节点索引leftChild和右孩子节点索引的关系如下：

parent = (leftChild - 1) / 2

leftChild = parent * 2 + 1

rightChild = parent * 2 + 2

与一般二叉树实现相比，我们可以随机访问任意结点即左右还是，而且可以很方便的访问每个节点的父亲节点。另外，为了计算方便，我们也可以从数组索引为1的位置开始存储，相应的节点间关系函数也要做出变化。。

三 添加和取出元素

1. add添加元素

从逻辑结构完全二叉树中来看，添加元素后为了保持堆的完全二叉树性质，需要在完全二叉树的末尾添加一个元素。对应到存储结构中，就是在数组的末尾添加一个元素。但是，在末尾位置添加元素后有可能破坏了堆的第二条性质，父亲节点大于或等于左右孩子。需要我们自己进行调整，以维持关系。具体做法：从末尾添加元素的位置开始，与父亲节点进行比较，如果大于父亲节点，则交换自己与父亲节点的位置。之后继续上述过程。直到达到合适位置，即小于或等于父亲节点或者达到根结点，即没有父亲节点时停止此过程

2. extractMax提取元素

提取元素只提取最大值，对于最大堆，即提取根结点位置的值。此是，根结点被删除，剩下左右两棵子树，融合两棵子树并且不破坏堆的性质，相对较难。一个比较有技巧的处理方式：使用堆中的末尾结点，替换根结点，之后删除根结点。此时，堆的第一个性质，完全二叉树得到了维持。但是，有可能破坏堆的第二个性质，父亲节点大于或等于左右孩子。需要我们自己进行调整，以维持关系。具体做法： 从根节点位置开始，父亲节点和左右孩子节点中的较大节点进行比较，如果父亲节点大于孩子中的较大节点，则交换父亲节点和该孩子节点，之后重复上述过程。直到达到合适位置， 即大于或等于左右孩子中的较大节点或者达到叶子节点为止

三 时间复杂度分析

添加元素add()：logn
提取元素extractMax()：logn

另外，堆的性质决定了堆是一棵完全二叉树，不可能退化成链表，最差时间复杂度就是logn，很高效。而二分搜索树平均时间复杂度在logn