C++数据结构堆排序的实现_c++建堆 - CSDN文库

5星 · 超过95%的资源 100 浏览量更新于2023-10-20 评论收藏 120KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

C++ 数据结构数据结构堆排序的实现堆排序的实现

堆排序（heapsort）是一种比较快速的排序方式，它的时间复杂度为O(nlgn)，并且堆排序具有空间原址性，任何时候只需要

有限的空间来存储临时数据。我将用c++实现一个堆来简单分析一下。

堆排序的基本思想为：堆排序的基本思想为：

1、升序排列，保持大堆；降序排列，保持小堆；

2、建立堆之后，将堆顶数据与堆中最后一个数据交换，堆大小减一，然后向下调整；直到堆中只剩下一个有效值；

下面我将简单分析一下：

第一步建立堆：

1、我用vector顺序表表示数组；

2、用仿函数实现大小堆随时切换，实现代码复用；

3、实现向下调整算法，时间复杂度为O（lgn）；

下面是我用某教材中的一个建最小堆的过程图，希望能更直观一些：

为了保证复用性，用仿函数重载了(),下面是复用的向下调整算法：

void _AdjustDown(int root,int size)

{

Camper camper; //仿函数

int parent = root;

int child = parent * 2 + 1;

while (child <= size) //保证访问不越界

{

if (child < size && camper(_vec[child+1] , _vec[child])) //保证存在右子树、同时判断右子树是否大于或小于左子树

{

child++;

}

if (camper(_vec[child], _vec[parent]))

{

swap(_vec[parent], _vec[child]);

parent = child;

child = parent * 2 + 1;

}

else

{

break;

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余3页未读，立即下载

评论10

Asama浅间

2023-06-14

这份文件的堆排序实现很实用，讲解也不是很难懂。

weixin_38689041

粉丝: 1
资源: 963

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈