考研算法30天:堆排序 【堆排序】

这篇具有很好参考价值的文章主要介绍了考研算法30天:堆排序 【堆排序】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

原先自己写过这道题的题解,但是当时水平有限所以这次重写一次。

(1条消息) 堆的创建(题目:堆排序)_空が笑っています的博客-CSDN博客

算法介绍

我在上陈越姥姥的课程之后我学会了如何用数组表示一个堆(堆其实就是根节点大于或者小于它的子节点的完全二叉树)然后陈越姥姥创建堆的思路是每次将新节点放到数组的最后然后通过和自己的父节点比较然后找到自己的位置然后插入。

void insert(int X){
    int i;
    for(i = ++size ; X<H[i/2] ; i = i/2){
        H[i] = H[i/2];
    }
    H[i] = X;
}

我觉得陈越姥姥的这个思路更加简单而且更容易理解的,如果一道题只需要插入的话,我觉得这个方式是最好的。 

但是看这道题它是需要你顺序排序的,那么我觉得最简单的思路有两种

第一种建立最小堆,然后每次将最小的(堆顶元素)弹出并输出。

第二种是建立最大堆,然后每次将最大的(堆顶元素)放入栈,然后根据栈先进后出的思路将元素弹出。(y总虽然没使用栈,但是我觉得思路差不多。)

我们很快发现不管是哪种方式,我们都需要删除的操作,所以姥姥的方式在这道题上就不太适用了。我们应该将这种调整元素位置的代码抽象出来并且可以用于删除。下面这种方式也是是从下面向上比较(每次父节点和自己的左右节点比较然后自己和自己的左右节点就在自己为根节点的二叉树中形成了堆,从n/2开始是因为下标比N/2大的节点是没有自己的子节点的了)

考研算法30天:堆排序 【堆排序】


void down(int u){
    int t=u;
    if(mysize >= u * 2 && h[t] > h[u * 2]) t = u * 2;
    if(mysize >= (u * 2 + 1) && h[t] > h[u * 2 + 1]) t = u * 2 + 1;
    if(t != u){
        swap(h[u],h[t]);
        down(t);
    }
}

算法题目

考研算法30天:堆排序 【堆排序】

#include <iostream>

using namespace std;

const int N = 1000010;
int q[N],sz;

void down(int x){
    //n/2就是有子节点最大的下标。
    //注意:这道题我们的n和size并不等价,size因为删除的原因
    //size会一直变。
    if(x>(sz/2))return;
    int t = x;
    //将根节点和其左右节点三者比较将最大的节点放到根节点上
    if(x*2<=sz  && q[x*2] > q[t]) t = x*2;
    if((x*2+1)<=sz && q[x*2+1] > q[t]) t = x*2 +1;
    if(t!=x){
        swap(q[t],q[x]);
        //如果下面子节点还有节点的话,就继续遍历
        //没有就返回,这道题上是不会有的,
        //因为我们一开始就是从n/2开始向下down的
        //而n/2就是有子节点最大的下标。
        down(t);
    }
}

void heap_sort(int n){
    sz = n;
    for(int i=n/2;i;i--) down(i);
    for(int i=n-1;i>=0;i--){
        //将根节点(最大的节点)和最后的节点交换位置
        swap(q[1],q[sz]);
        //然后删除最大的节点。
        sz--;
        //因为刚才将最后的节点放到了根节点的位置
        //所以我们需要从1开始向下再down一次
        down(1);
    }
    return;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&q[i]);
    heap_sort(n);
    for(int i=1;i<=n;i++)printf("%d ",q[i]);
    return 0;
}

考研算法30天:堆排序 【堆排序】

 文章来源地址https://www.toymoban.com/news/detail-508782.html

到了这里,关于考研算法30天:堆排序 【堆排序】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 自己写过比较蠢的代码:从失败中学习的经验

    🎉 自己写过比较蠢的代码:从失败中学习的经验 ☆* o(≧▽≦)o *☆嗨~我是IT·陈寒🍹 ✨博客主页:IT·陈寒的博客 🎈该系列文章专栏:Java面试技巧 📜其他专栏:Java学习路线 Java面试技巧 Java实战项目 AIGC人工智能 数据结构学习 🍹文章作者技术和水平有限,如果文中出现错

    2024年02月07日
    浏览(29)
  • 考研算法第十三天:二叉排序树 【二叉排序树的插入和遍历】

    这道题很妙。题目给的二叉排序树好像没学过其实就是二叉查找树。然后这道题主要的就是思路     1.先找到那个要删除节点所在处     2.找到之后处理分三种情况     删除的节点是叶节点,直接删除即可     删除的节点只有右节点或者左节点 将左节点或者右节点删除即可

    2024年02月05日
    浏览(46)
  • 【数据结构入门精讲 | 第九篇】考研408排序算法专项练习(一)

    前面几篇文章介绍的是排序算法,现在让我们开始排序算法的专项练习。 1.希尔排序是稳定的算法。(错) 解析:稳定性是指如果两个元素在排序前后的相对顺序保持不变,那么这个排序算法就是稳定的。对于具有相同的元素,排序后它们的相对位置应该保持不变。

    2024年02月03日
    浏览(46)
  • 过去一周写过的算法题的一部分(dfs,贪心)

    (首先说明一点哈:这是我第一次写博客,写的不好大家见谅) 自我介绍:一个脑子不好的大一学生,c语言接触还没到半年,若涉及到效率等问题,各位都可以在评论区提出见解,谢谢啦 (题目链接:P1135 奇怪的电梯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)) 我一开始用

    2024年02月03日
    浏览(29)
  • 考研证件照可以自己用手机拍吗?考研证件照p过可以通过审核吗?考研证件照有什么要求

    现在的智能手机相机技术先进,大多都配备了高像素摄像头,使得自拍照片的质量有了大幅提升。相较于传统的证件照拍摄,使用手机自拍考研证件照理论上是可行的。然而,考研证件照需要满足一定的规定和标准,包括照片的背景颜色、人物的服装、姿势等方面。 在拍摄考

    2024年02月19日
    浏览(72)
  • 考研数据结构:第八章 排序

    2.1.1算法思想 插入排序的思想很简单,就是不断的把一个个带排序的记录,按的大小插入到前面已经排好序的子序列中。直到全部序列插入完成。 比如我们现在要对下面的序列进行排序, 刚开始我们从1号位开始 我们会认为当前处理的这个元素之前都是有序的 现在把

    2024年02月11日
    浏览(37)
  • 在思想方面讨论堆排序(考研自用,按非递减方式排序)

      目录 1.什么是排序 2.关于堆排序的几个问题 3.问题求解 首先:排序的定义     拿冒泡排序(递增)来讲,在一个给定的数组序列中,若A[i+1]A[i],则将其两个的数值进行交换,排好序的序列应该是递增的,类似于[1,2,3,4,5...]; 所以排序是在数组中进行的,物理内存的数值发生了永久性的变

    2024年02月05日
    浏览(44)
  • 34岁上岸,我终于圆了自己的考研梦

    ​ 大家好,我是独孤风,一位曾经的港口煤炭工人,目前在某国企任大数据负责人,公众号大数据流动的作者。 ​ 虽然告诉自己要平静,但是当接到EMS录取通知书的那一刻,眼眶还是忍不住有些湿润。今年正好是是东北大学的建校100周年,录取通知书还附赠了小礼物。 ​

    2024年02月11日
    浏览(25)
  • [保研/考研机试] KY30 进制转换-大整数转二进制 清华大学复试上机题 C++实现

    将一个长度最多为30位数字的十进制非负整数转换为二进制数输出。 输入描述: 多组数据,每行为一个长度不超过30位的十进制非负整数。 (注意是10进制数字的个数可能有30个,而非30bits的整数) 输出描述: 每行输出对应的二进制数。 仍然是“除2取余法”,主要的区别在

    2024年02月13日
    浏览(80)
  • 五月集训(第30天) —— 拓扑排序

            此为《英雄算法联盟:算法集训》的内容,具体内容详见:知识星球:英雄算法联盟。加入星球后,即可享用星主 CSDN付费专栏 免费阅读 的权益。         欢迎大家积极在评论区留言发表自己的看法,知无不言,言无不尽,养成每天刷题的习惯,也可以自己发

    2024年02月09日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包