首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >完全二叉树

完全二叉树

作者头像
狼啸风云
修改2022-09-03 19:43:23
6580
修改2022-09-03 19:43:23
举报

堆常用来实现优先队列。 用数组保存数据,而不是链表。

在队列中,操作系统调度程序反复提取队列中第一个作业并运行,因为实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

堆的实现通过构造二叉堆(binary heap),实为二叉树的一种(完全二叉树) 完全二叉树:若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树

大根堆和小根堆

最大(最小)堆是一棵每一个节点的键值都不小于(大于)其孩子(如果存在)的键值的树。大顶堆是一棵完全二叉树,同时也是一棵最大树。小顶堆是一棵完全完全二叉树,同时也是一棵最小树。

将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

  • 堆中任一子树亦是堆。
  • 以上讨论的堆实际上是二叉堆(Binary Heap),类似地可定义k叉堆。

如下图所示,图一为最大堆,图二为最小堆:

基本操作

  • 上浮 shift_up;
  • 下沉 shift_down
  • 插入 push
  • 弹出 pop
  • 取顶 top
  • 堆排序 heap_sort

以小根堆为例: 堆可以用数组存储数据,如有数组:{8,5,2,9,3,7,1,4,6} 则可以构成堆:

image.png

可以发现:任意节点的左右孩子对应数组下标的一半为其父节点对应的下标(5/2==4/2==2)。 注意:这里下标从1开始计算而不是从0开始,因为从0开始的话根节点的下标和子节点下标间就没有了倍数关系(5/2 != 6/2)

上浮

从当前结点开始,和它的父亲节点比较,若是比父亲节点来的小,就交换,然后将当前询问的节点下标更新为原父亲节点下标;否则退出。

下沉

经过上浮操作之后,下标3处节点的元素值如下图所示

让当前结点的左右儿子(如果有的话)作比较,哪个比较小就和它交换,并更新询问节点的下标为被交换的儿子节点下标,否则退出。

插入

每次插入的时候呢,都往最后一个插入,然后使它上浮。

弹出(删除根节点元素)

让根节点元素和尾节点进行交换,然后让现在的根元素下沉就可以了。

取顶

根节点数组下标必定是 0,返回堆数组中下标为 0 的元素即可。

堆排序

见算法 - 排序系列文章第六篇,同时用代码实现上述对堆的操作。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-11-21 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 大根堆和小根堆
  • 基本操作
    • 上浮
      • 下沉
        • 插入
        • 弹出(删除根节点元素)
          • 取顶
            • 堆排序
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档