您的位置:首页 > 房产 > 建筑 > 河南最新建设工程信息_国家市场监督管理总局合同示范文本库_可以看任何网站的浏览器_软文推荐

河南最新建设工程信息_国家市场监督管理总局合同示范文本库_可以看任何网站的浏览器_软文推荐

2025/3/14 11:07:56 来源:https://blog.csdn.net/graceyun/article/details/146230341  浏览:    关键词:河南最新建设工程信息_国家市场监督管理总局合同示范文本库_可以看任何网站的浏览器_软文推荐
河南最新建设工程信息_国家市场监督管理总局合同示范文本库_可以看任何网站的浏览器_软文推荐

目录

  • 1 堆的应用
    • 1.1 堆排序
      • 1.1.1 思路
      • 1.1.2 代码实现
    • 1.2 建堆的时间复杂度
      • 1.2.1 向下调整
      • 1.2.1 向上调整
      • 1.2.3 结论

学习堆的应用之前,欢迎学习下堆。
这是博主之前的文章,欢迎学习交流

初阶数据结构(C语言实现)——5.2 二叉树的顺序结构及堆的实现
初阶数据结构(C语言实现)——5.1二叉树基础概念

1 堆的应用

1.1 堆排序

1.1.1 思路

堆排序即利用堆的思想来进行排序,总共分为两个步骤:

  1. 建堆
    升序:建大堆
    降序:建小堆
  2. 利用堆删除思想来进行排序
    建堆和堆删除中都用到了向下调整,因此掌握了向下调整,就可以完成堆排序。
    在这里插入图片描述

在这里插入图片描述

1.1.2 代码实现

void swap(HPDataType* p1, HPDataType* p2)
{HPDataType x = *p1;*p1 = *p2;*p2 = x;
}void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;//根据孩子位置,计算父亲位置while (child > 0)//child = 0,说明parent不存在了,已经到堆顶了{if (a[child] > a[parent]) //当孩子大小大于父亲大小的时候就交换{swap(&a[child], &a[parent]);//因为其他地方也要用到交换,封装了一个交换函数child = parent; //现在把父亲的值给孩子。parent = (child - 1) / 2;//继续计算现在节点的父亲结点,}else//孩子<=父亲 没必要往上走,直接break就行。		{break;}}
}
void AdjustDown(HPDataType* a, int n ,int parent)
{int child = parent*2+1;//根据父亲位置,计算孩子位置while (child <n)//走到没有孩子的时候,结束,{// 选出左右孩子中大的那一个if (child + 1 < n && a[child + 1] > a[child])//必须把child+1<n放前面,否则后面a[child+1]就越界了!{++child;}//交换if (a[child] > a[parent]){swap(&a[child],&a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
// 排升序 -- 建大堆void Heapsort(int* a, int n)//参数:数组和数据个数
{//建堆,方法1:向上调整堆 //模拟的是插入数据的过程for (int i = 1; i < n; ++i){AdjustUp(a, i);}//建堆,方法2:向下调整堆for (int i = 1; i < n; ++i){AdjustDown(a, n , i);}int end = n - 1;while (end > 0){swap(&a[end], &a [0]);AdjustDown(a, end, 0);--end;}
}

1.2 建堆的时间复杂度

1.2.1 向下调整

因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值,多几个节点不影响最终结果):

在这里插入图片描述

因此:向下建堆的时间复杂度为O(N)。

1.2.1 向上调整

在这里插入图片描述

因此向上建堆的时间复杂度是N*logn

1.2.3 结论

向下调整时间复杂度更小,更优,所以建堆使用的是向下调整

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com