堆排序

思路:

        1、把无序数组构建成最大二叉堆

        2、循环删除堆顶元素,移到集合尾部,调节堆产生新的堆顶

当我们删除一个最大堆的堆顶(并不是完全删除,而是替换到最后面),经过自我调节,第二大的元素就会被交换上来,成为最大堆的新堆顶。

正如上图所示,当我们删除值为10的堆顶节点,经过调节,值为9的新节点就会顶替上来;当我们删除值为9的堆顶节点,经过调节,值为8的新节点就会顶替上来.......

由于二叉堆的这个特性,我们每一次删除旧堆顶,调整后的新堆顶都是大小仅次于旧堆顶的节点。那么我们只要反复删除堆顶,反复调节二叉堆,所得到的集合就成为了一个有序集合,

code
run
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 堆排序可以做什么 首先应该弄清楚堆排序可以解决什么问题,答案是显而易见的:排序。说得通俗点儿就是对一组无序的数字进...
    Springlord888阅读 30,434评论 11 52
  • 堆是一棵满足一定性质的二叉树,具体的讲堆具有如下性质:父节点的键值总是不大于它的孩子节点的键值(小顶堆), 堆可以...
    9527Roy阅读 667评论 0 0
  • 原文链接 堆排序可以做什么 首先应该弄清楚堆排序可以解决什么问题,答案是显而易见的:排序。说得通俗点儿就是对一组无...
    只为此心无垠阅读 599评论 0 0
  • 堆排序和快速排序一样也是一个O(n logn)的排序算法 但是二者是不一样的实现原理 [这是肯定的,不要pia我]...
    阿飞不理飞阅读 759评论 0 0
  • 相传,程邈是做秦朝的县狱吏(负责文书一类的差事)的工作的,相当于如今的秘书。他个性耿直,因此得罪了皇帝,被皇帝关进...
    青梅竹酒阅读 269评论 0 3