首页 > 试题广场 >

n个节点的满二叉树调整成一个最小堆的最优复杂度

[单选题]

n 个节点的满二叉树调整成一个最小堆的最优复杂度

查看答案及解析

不做人了

平均复杂度 NlogN

确定一个数的位置logN

N个数 NlogN

最优复杂度刚好顺序

N/2

编辑于 2020-06-17 10:46:58 回复(2)

走位崴了脚

N个节点，分支节点N/2，每个分支最多进行两次比较和互换操作，因此整个构建过程时间复杂度为N

发表于 2021-03-17 22:42:31 回复(1)

我的天鸭

从有子节点的节点开始由低到高依次调整，O（n）

发表于 2019-08-27 10:42:33 回复(3)

GoAshore

建堆复杂度O(n)

发表于 2022-11-30 17:05:13 回复(0)

牛蛙…

N个节点，分支节点N/2，每个分支最多进行两次比较和互换操作，因此整个构建过程时间复杂度为N

发表于 2021-10-09 20:36:51 回复(0)

骑着毛驴来学习

将二叉树转化成最大堆或最小堆：
最大堆：
1.堆树是一颗完全二叉树
2.父节点总是大于或等于他的孩子节点

3.堆树中每个节点的子树都是堆树。

最小堆：
1.堆树是一颗完全二叉树
2.父节点总是小于或等于他的孩子节点
3.堆树中每个节点的子树都是堆树。

发表于 2021-03-08 07:21:09 回复(0)

提交观点

问题信息

小米集团算法工程师树 2018

来自：小米2018春季实习生...

上传者：小小

难度：

6条回答 382收藏 2457浏览

扫一扫，把题目装进口袋