最大堆最小堆

堆

堆给人的感觉是一个二叉树，但是其本质是一种数组对象，因为对堆进行操作的时候将堆视为一颗完全二叉树，树种每个节点与数组中的存放该节点值的那个元素对应。所以堆又称为二叉堆，堆与完全二叉树的对应关系如下图所示：

通常给定节点i，可以根据其在数组中的位置求出该节点的父亲节点、左右孩子节点，这三个过程一般采用宏或者内联函数实现。书上介绍的时候，数组的下标是从1开始的

根据节点数值满足的条件，可以将分为最大堆和最小堆。
把堆看成一个棵树，有如下的特性：

保持堆的性质

堆个关键操作过程是如何保持堆的特有性质，给定一个节点i，要保证以i为根的子树满足堆性质。书中以最大堆作为例子进行讲解，并给出了递归形式的保持最大堆性的操作过程。先从看一个例子，操作过程如下图所示：

从图中可以看出，在节点i=2时，不满足最大堆的要求，需要进行调整，选择节点2的左右孩子中最大一个进行交换，然后检查交换后的节点i=4是否满足最大堆的要求，从图看出不满足，接着进行调整，直到没有交换为止。

建堆

建立最大堆的过程是自底向上地调用最大堆调整程序将一个数组A[1…N]变成一个最大堆。将数组视为一颗完全二叉树，从其最后一个非叶子节点（n/2）开始调整。调整过程如下图所示：

堆排序算法

堆排序算法过程为：先调用创建堆函数将输入数组A[1…n]造成一个最大堆，使得最大的值存放在数组第一个位置A[1]，然后用数组最后一个位置元素与第一个位置进行交换，并将堆的大小减少1，并调用最大堆调整函数从第一个位置调整最大堆。给出堆数组A={4,1,3,16,9,10,14,8,7}进行堆排序简单的过程如下：

创建最大堆，数组第一个元素最大，执行后结果下图：
进行循环，从总长度到2，并不断的调整最大堆，给出一个简单过程如下：

问题

在创建最大堆的过程中，为什么从最后一个非叶子节点（n/2）开始到第一个非叶子结束，而不是从第一个非叶子节点（1）到最后一个非叶子节点（n/2）结束呢？

我的想法是：如果是从第一个非叶子节点开始创建堆，有可能导致创建的堆不满足堆的性质，使得第一个元素不是最大的。这样做只是使得该节点的和其左右孩子节点满足堆性质，不能确保整个树满足堆的性质。如果最大的节点在叶子节点，那么将可能不会出现在根节点中。例如下面的例子：

从图中可以看出，从第一个非叶子节点开始创建最大堆，最后得到的结果并不是最大堆。而从最后一个非叶子节点开始创建堆时候，能够保证该节点的子树都满足堆的性质，从而自底向上进行调整堆，最终使得满足最大堆的性质。

总结

对于最大堆建立的时候，需要主要的是，开始建立的时候都是从最后一个非叶子节点向上（数组向前）进行建立堆，这样做的目的是，可以让叶子节点的最大数据通过调整到根节点上。
如果从第一个根节点开始建立堆的话，那么如果最大节点在叶子节点，这样调整将不能导致最大数据调整到根节点上，因为只能保证当前的节点和叶子节点的大小调整，调整完根节点这个节点，之后就没有调整了