堆排

• 什么是堆
• • 建堆的两种方式
  • • 方式一:
    • 方式二:
  • 堆排的实现
  • • 时间复杂度的分析

什么是堆

堆是具有以下性质的完全二叉树
1，每个结点的值都大于或等于其左右孩子结点的值，这种堆称为大堆。
2，每个结点的值都小于或等于其左右孩子结点的值，这种堆称为小堆。
如下图所示：

建堆的两种方式

要是实现堆排，就先要对数据进行建堆处理，也就是将原本混乱无章的数据，通过建堆的手段，建成大堆或者小堆，以便接下来堆排的实现。

一下两种方式建的都是大堆

方式一:

假设给出的数据是：{45,13,8,10,20,18,50}
将该数据以堆的形式展现出来的结果如图：

第一种方式向上调整：

void Adjustup(int* a, int child)
{assert(a);int parent = (child - 1) / 2;//父亲结点while (child > 0){if (a[child] > a[parent])//小于就是建小堆{//大的数据向上走swap(a[child], a[parent]);//交换位置child = parent;parent = (child - 1) / 2;}elsebreak;}
}void heapsort1(int* a, int sz)
{//时间复杂度O(n*logn)for (int i = 1; i < sz; ++i){Adjustup(a, i);}
}

解释：
遍历数组，通过传入孩子结点的位置(i=0时可以省略)，找到父亲结点的位置，如果该孩子结点的值大于父亲结点的话，就交换两个数据。然后更孩子结点到父亲结点上，再通过新的孩子结点更新父亲结点的位置。

循环结束的条件就是孩子结点的大于0，注意不能等于0如果child等于0时还进行循环的话，a[parent]就会造成越界。

父亲结点和孩子结点之间的规律关系如下：
parent = (child - 1) / 2;
left_child = 2 * parent + 1;
right_child = 2 * parent + 2;
大家可以带入验证一下！

i = 1时，向上调整的过程如下：

child为1的时候，该孩子结点的值为13，并不大于其父亲结点45，同理i = 2时也是如此。
i= 3时，孩子结点来到10的位置，通过parent = (child - 1) / 2; 计算出父亲结点是13，并不大于该父亲结点也是直接break。
i = 4时，孩子结点就是20，大于其父亲结点13，那么交换位置，并更新孩子结点和父亲结点，如下图：

更新之后的孩子结点是20，大于其父亲结点45，循环break;结束。
后面的18，和50也是如此，如果孩子结点大于当前孩子结点的父亲结点就交换，并且更新孩子和父亲的位置，再进行判断。直到孩子结点<=0，或者break跳出循环。

建完之后的大堆如下所示：

时间复杂度：O(N logN)。

方式二:

第一种方式是通过传的孩子结点，然后通过该孩子结点去找父亲结点，然后进行比较。

第二种方式可以说与第一种方式相反。
向下调整：

void Adjustdown(int* a, int sz, int parent)
{//先假设左孩子是左右孩子中最大的int max_child = 2 * parent + 1;while (max_child < sz){//max_child + 1 < sz  一定要加，防止已经有序的数据再次参与到新一轮的排序中//比如右孩子已经来到了正确的位置时，已经比左孩子大，那么就会导致右孩子又被迫参与到排序中了//导致数据混乱if (max_child + 1 < sz && a[max_child] < a[max_child+1]){max_child++;}if (a[max_child] > a[parent]){swap(a[max_child], a[parent]);parent = max_child;max_child = 2 * parent + 1;//还是假设左孩子是最大的}elsebreak;}
}//数组的引用必须要指定其大小 -- 这里就不建议使用这种方式了
void heapsort2(int* a, int sz)
{//时间复杂度O(n)for (int i = (sz-1-1) / 2; i >= 0; --i){Adjustdown(a, sz, i);}
}

这次我们在调用的是Adjustdown(a, sz, i);函数，第一个参数和第二个参数分别是函数名和数组的大小，等会解释为什么要传入数组的大小。
第三个参数为父亲结点，该父亲结点是数组中最小的一个父亲，即通过数组最后一个元素计算出来的父亲结点，如下图所示：

数组的最后一个元素的下标是6，（6-1）/ 2 = 2。下标为2的元素也就是8。

向下调整的思路为：
通过传入的父亲结点去找孩子结点中，最大的孩子，与最大的孩子结点的值进行比较，如果小于其最大的孩子结点就发生交换。然后更新父亲结点，再通过新的父亲结点去更新孩子结点。

此时父亲结点来到最后一个位置，这时候再去更新孩子结点的时候，孩子结点就会超出数组的大小，我们也是用此作为循环结束的条件的。所以数组的大小也要进行传入。

我们不难发现 - - i之后，父亲结点就会来到13的位置。
其实两种建堆实现的思路都是大致相同的，只不过一种是通过孩子找父亲，一种是通过父亲找孩子中最大的。

大家通过画图的方式去走一遍上面的数据，有助于大家更好的理解这两种方式。

时间复杂度：O(N)

堆排的实现

有了建堆的基础，我们就可以来写堆排序了，其实堆排序的主要环节就在建堆上面，堆排是容易的。
因为向下调整建堆的时间复杂度更低，所以我们就使用向下建堆的方式来实现堆排。

此时建成的大堆如下图所示（默认实现的是升序）：

堆排思路：
1，将堆顶元素和堆底元素进行交换，这次交换的意义就在于，最大的元素来到了最后的位置。
2，删除最后的元素，再进行建堆，此删除并非真的将该元素从数组中抹去，而是这个元素不参与下一次的建堆。
第二步执行完之后，新的大堆就建好了，结果如下：

建完堆之后，数组中第二大的数据45就来到了堆顶的位置，此时再进行第一步，我们就会发现45来到了倒数第二的位置，然后循环上述的过程就能完成堆排。

代码：

void Adjustdown(int* a, int sz, int parent)
{//先假设左孩子是左右孩子中最大的int max_child = 2 * parent + 1;while (max_child < sz){//max_child + 1 < sz  一定要加，防止已经有序的数据再次参与到新一轮的排序中//比如右孩子已经来到了正确的位置时，已经比左孩子大，那么就会导致右孩子又被迫参与到排序中了//导致数据混乱if (max_child + 1 < sz && a[max_child] < a[max_child+1]){max_child++;}if (a[max_child] > a[parent]){swap(a[max_child], a[parent]);parent = max_child;max_child = 2 * parent + 1;//还是假设左孩子是最大的}elsebreak;}
}//数组的引用必须要指定其大小 -- 这里就不建议使用这种方式了
void heapsort2(int* a, int sz)
{//时间复杂度O(n)for (int i = (sz-1-1) / 2; i >= 0; --i){Adjustdown(a, sz, i);}int end = sz - 1;while (end){swap(a[0], a[end]);Adjustdown(a, end, 0);//重新建堆end--;}
}

时间复杂度的分析

上面们已经知道向下调整建堆的时候的时间复杂度为O(n)，再加上我们堆排需要遍历一遍数组知道最后一个数据，所以整体的时间复杂度为O(N logN)。

只要大家能掌握向下调整建堆的方式，并且知道还有向上建堆的方式就可以，我们肯定是选择时间复杂度更低的算法来实现堆排。