堆排序

Question

老师我有点疑惑，堆排序是O(nlogn)而二叉堆的取出操作是O(logn)，说明直接取出来用于排序是优于堆原地排序的，那么为什么还要进行堆排序呢？

Answer 1

liuyubobobo 2020-06-15 10:06:41

抱歉，我没有理解你的意思？什么叫直接取出来用于排序？

• 提问者 qq_萌新_4 #1

  就是说每次extract操作都是取出最大值，相当于进行了一次排序

• liuyubobobo 回复 提问者 qq_萌新_4 #2

  不是原地的。其实堆排序的本质也是每次 extract 出一个元素，但使用了一个小技巧，原地完成。

• 提问者 qq_萌新_4 回复 liuyubobobo #3

  那按照时间复杂度来说直接取性能会快一点呀

点开查看后面1条评论