关于堆排序算法时间、空间复杂度问题

Question

如题！！！使用堆排序算法时间、空间复杂度哪位大侠指点一二 

Answer 1

在构建堆的过程中，因为我们是完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和若有必要的互换，对于每个非终端结点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为O(n)。在正式排序时，第i次取堆顶记录重建堆需要用O(logi)的时间（完全二叉树的某个结点到根结点的距离为.log2i.＋1），并且需要取n－1次堆顶记录，因此，重建堆的时间复杂度为O(nlogn)。

Answer 2

时间复杂度如1L所说，是O（nlogn)
堆排序(以最小堆为例)每次将最小元素上升到堆顶，获取之，然后删除改元素，把堆中最后一个元素放到堆顶，重复上述操作。由于在排序中只存在1个元素的交换，所以空间复杂度为O（1）