脸熟跪经

BullMonk 发表于 2017-11-13 08:38
第二题原数列无序，但是你生成的树不是heap，所以总可以满足，我是这样子的，每次找最大点作为root，把数 ...

老哥，如何每次找到最大值？遍历的话，如果原来就是有序的时间复杂度岂不是O(n!), 用heap的话，每次弹出来的两个最大值都在右半边怎么办 ？

向上的牛牛 发表于 2017-11-13 06:16
楼主能说一下第二题那个array to max-heap是怎么做的吗？

你看了楼主的回复了吗？ 请问如何每次找到最大值？遍历的话，如果原来就是有序的时间复杂度岂不是O(n!), 用heap的话，每次弹出来的两个最大值都在右半边怎么办 ？

楼主厉害 点赞点赞点赞

真淘蛮 发表于 2017-11-13 10:32
你看了楼主的回复了吗？ 请问如何每次找到最大值？遍历的话，如果原来就是有序的时间复杂度岂不是O(n!),  ...

应该是直接pass through一遍找最大值吧。然后这里的heap并不是真正意义上的heap，并不要求是一个complete tree， 其只要满足父大于子的性质就可以了。所以时间复杂度应该是O（nlogn）吧。

向上的牛牛 发表于 2017-11-13 10:44
应该是直接pass through一遍找最大值吧。然后这里的heap并不是真正意义上的heap，并不要求是一个complete ...

我说错了，如果是一个递增的序列， 根是最后一个，每次建节点不都得找这半部分的最大节点吗？所以难道不是O(n * n)  吗？比如1，2，3，4，5
树不应该是 ：
                    5
                  4
                3
              2
           1

请问lz多久收到消息的？hr有把你送hiring committee review吗？