数据结构之堆排序
堆排序
版本一
- 基于已有数组建堆
- 取堆顶元素并删除堆顶元素重新建大根堆，完成排序版本。
图文理解
版本二
前提：必须提供有现成的数据结构堆
数组建堆，首尾交换，交换后的堆尾数据从堆中删掉，将堆顶数据向下调整选出次大的数据。
向下调整建堆
- 先把每棵子树通过向下调整算法建成大根堆；
- 整体建成大根堆结构。
for (int i = (n - 1 - 1) / 2;i >= 0;i--)
{
AdjustDown(arr, i, n);
}void AdjustDown(HPDataType* arr, int parent, int n)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && arr[child] < arr[child + 1])
{
child++;
}
//>建小堆
//<建大堆
if (arr[parent] < arr[child])
{
Swap(&arr[parent], &arr[child]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}向上调整建堆
- 堆顶元素开始建堆；
- 通过将每一个结点进行建大根堆，最后整体就是大根堆结构。
通过顺序结构二叉树文章可知，向下调整算法的时间复杂度优于向上调整算法，因此更推荐用向下调整建堆。
for (int i = 0;i < n;i++)
{
AdjustUp(arr, i);
}//向上调整
void AdjustUp(HPDataType* arr, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
//>:大堆
//<:小堆
if (arr[child] > arr[parent])
{
//交换
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
排升/降序
排成升序结构，建大根堆； 排成降序结构，建小根堆。
升序
int end = n - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, 0, end);
end--;
}注:当前是大根堆结构
- 将堆顶数据与末端数据交换；
- 重新建成大根堆结构，保证下次取到的堆顶数据依然是最大值；
- 最后数据将会排成升序结构。
那么，降序结构原理也类似上图所示。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-01-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
