扫描二维码,下载手机APP
下载安卓APP箭头
客服QQ
箭头给我发消息

客服QQ:3315713922
论坛 >编程语言 >数据结构&算法实践—堆排序

数据结构&算法实践—堆排序

spring发布于 2018-04-27 09:39查看:10993

排序>>选择排序>>堆排序

List:

image.png

  1. start

基本概念:

1524792969621451.gif

image.png

堆为一棵完全二叉树,每个节点值都>=子节点值

堆排序根据这个特性,首先将所有元素建立堆,然后一个个取出,即有序的

堆中每个节点的位置:

image.png

最大堆主要操作逻辑:

插入:将新元素加入完全二叉树最后一个节点,依次往上,调整直到满足父节点值都>=子节点值

删除:移除根节点,将最后一个节点拿到根节点,依次往下,调整

原始:

image.png

插入操作:12,先假定放在最后一个位置,然后从这个节点开始往上,同父节点比较,依次调整

image.png

删除:取走11,将最后一个元素8移到根节点,从上往下,重新调整

image.png

  1. start

根据公式,我们可以使用数组模拟实现完全二叉树(不使用首个位置)

首先,我们先实现堆:

image.png

image.png

然后,实现排序过程:

image.png


收藏(0)0
查看评分情况

全部评分

此主贴暂时没有点赞评分

总计:0

回复分享

版主推荐

    共有0条评论

      • 课课家运营团队
      • Mr ken
      • YUI
      • cappuccino
      • mr jack
      • IT宅男
      • Mright
      • 课课家软考1
      • 选择版块:

      • 标题:

      • 内容

      • 验证码:

      • 标题:

      • 内容

      • 选择版块:

      移动帖子x

      移动到: