侧边栏壁纸
博主头像
雨探青鸟博主等级

遥知蓬山雨途险 却看青鸟意决探

  • 累计撰写 61 篇文章
  • 累计创建 67 个标签
  • 累计收到 19 条评论

目 录CONTENT

文章目录

数据结构之选择排序

雨探青鸟
2022-10-29 / 0 评论 / 0 点赞 / 89 阅读 / 313 字
温馨提示:
本文最后更新于 2023-04-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

简单选择排序

堆排序

大根堆与小根堆

 把堆看作一个完全二叉树

  • 大根堆:父节点大于两个子节点
  • 小根堆:父节点小于两个子节点

建立大根堆

  • 下沉操作:对于节点n

    • 节点n大于所有的孩子或者节点n没有孩子,就不用操作直接退出,否则进行下面
    • 交换节点n与节点n的大孩子m,然后对m进行同样的操作
  • 对于一个无序堆:从最后一个度不为0的节点开始一直递减到根节点,依次进行下沉操作

大根堆的插入

  • 上升操作:对节点n

    • 比较节点n与其父亲,如果小于等于其父亲或者节点n已经是根节点了,则不用操作退出。否则进行下面步骤
    • 交换节点n与其父亲m,然后对m进行上升操作
  • 首先插入到最后的位置,然后进行上升操作

大根堆的删除

  • 删除首个元素:交换根节点与最后一个节点,然后对根节点进行下沉操作
0

评论区