数据结构：堆排序

更完堆，再更一期堆排序

利用容器实现堆排序

在C++等高级语言中，基本上都有堆或者优先队列等容器，借助这些容器很容易实现堆排序。

将数组里面的元素先插入到容器中，建好堆，
接着将容器中的元素，按照升序或降序重新放回数组中
即可实现好排序

#include <iostream>
#include <queue>using namespace std;int main()
{int a[] = { 2,1,4,2,5,5,1,2,3,5,3,2,3,22,31,4,213,12 };//默认建大堆降序//priority_queue<int> pq;//建小堆，可升序priority_queue<int, vector<int>, greater<int>> pq;for (auto e : a){pq.push(e);}int i = 0;while (!pq.empty()){a[i++] = pq.top();pq.pop();}for (auto e : a){cout << e << " ";}cout << endl;return 0;
}

在这里插入图片描述

利用容器实现堆排序的缺点

1、空间复杂度较高，O(N)
2、万一面试的时候面试官让你手写堆排序，不能使用容器，就很尴尬了。

利用数组原地实现堆排序（手写堆排序）

首先，我们需要模拟建堆，将数组建成一个堆。

这里有两种方法，向上建堆和向下建堆。

向上建堆

我们向上调整建堆，就需要调整之前本身就是一个堆，不破坏堆的性质，
那么我们就可以直接从第二个元素开始，每一个元素都向上调整，一直去维护这个堆。
（第一个元素不用调整，本身就是一个堆）

向上调整算法在上一篇文章《数据结构：堆》中有所提及，这里就不详细介绍了
传送门：数据结构：堆

向上建堆代码：

void AdjustUp(int* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] > a[parent]){swap(a[child], a[parent]);child = parent;parent = (parent - 1) / 2;}else break;}
}int main()
{int a[] = { 2,1,4,2,5,5,1,2,3,5,3,2,3,22,31,4,213,12 };int n = sizeof(a) / sizeof(a[0]);for (int i = 1; i < n; ++i){AdjustUp(a, i);}
return 0;
}

向下建堆

我们向下建堆，要求左右子树都是堆，才能完成向下调整建堆。
那么我们从最后一个非叶子节点开始向下调整建堆，一直向前，直到根节点。
（叶子节点没有子树，不用向下调整建堆）

向下调整算法在上一篇文章《数据结构：堆》中有所提及，这里就不详细介绍了
传送门：数据结构：堆

向下建堆代码：

void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child] < a[child + 1]){child++;}if (a[child] > a[parent]){swap(a[child], a[parent]);parent = child;child = child * 2 + 1;}else break;}
}int main()
{int a[] = { 2,1,4,2,5,5,1,2,3,5,3,2,3,22,31,4,213,12 };int n = sizeof(a) / sizeof(a[0]);for (int i = (n - 1 -1) /2; i >= 0; --i){AdjustDown(a, n, i);}return 0;
}

理性分析一下向上建堆和向下建堆的时间复杂度

算时间复杂度，要考虑最坏情况，这里以满二叉树为例
假设共h层高度

向上建堆

从第二层开始，都需要向上移动柜（k-1）层
每层的个数是2^k-1 ，每一层需要移动的次数就是2^k-1 * (k-1)
把每一层相加求和即可，
最后，时间复杂度是关于n的函数，最后把h换成n即可。

以下为草稿借鉴
在这里插入图片描述

向下建堆

从倒数第二层开始，每一层向下调整 h - k层
每层的个数是2^k-1 ，每一层需要移动的次数就是2^k-1 * (h - k)
把每一层相加求和即可，
最后，时间复杂度是关于n的函数，最后把h换成n即可。

向下建堆草稿借鉴：
在这里插入图片描述

综上，向上建堆的时间复杂度是O(N*logN)，向下建堆的时间复杂度是O(N)，差距十分显著。
所以，我们采用向下建堆算法。

感性分析一下为啥向下调整算法效率更高

我们可以发现，

向上调整建堆，越下面调整的次数越多，但是越下面每一层的个数却越多，这就是多 * 多
向下调整建堆，越下面调整的次数越少，但是越下面每一层的个数却越少，这就是多 * 少

可以联系田忌赛马去理解。

升序建大堆，降序建小堆

看到标题，我相信很多小伙伴都不理解，为啥升序建大堆，不应该升序建小堆吗？
且听我慢慢分析

注意，我们需要不借助容器，也就是在原地进行排序。
如果升序建小堆，那么我们找到了最小的元素，怎么找次小的元素呢，怎么找再次小的元素呢？
比如一个小堆
1 2 10 112 111 3 ……
这样会破坏堆的性质，是不可取的

如果升序建大堆有什么好处呢？

假设一个大堆：
213 12 31 4 5 5 22 2 3 5 3 2 3 4 1 2 2 1
我们有最大的元素，
将其与最后一个元素交换，size–
将此时的第一个元素进行向下调整算法，就又可以维护堆的性质。
依此循环，就可以排好序了。

降序建小堆同理，这里就不分析了。

堆排序代码（升序为例）

void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child] < a[child + 1]){child++;}if (a[child] > a[parent]){swap(a[child], a[parent]);parent = child;child = child * 2 + 1;}else break;}
}int main()
{int a[] = { 2,1,4,2,5,5,1,2,3,5,3,2,3,22,31,4,213,12 };int n = sizeof(a) / sizeof(a[0]);for (int i = (n - 1 -1) /2; i >= 0; --i){AdjustDown(a, n, i);}int end = n - 1;while (end){swap(a[end], a[0]);--end;AdjustDown(a, end + 1, 0);}
return 0;
}

在这里插入图片描述