Question

堆排序时间复杂度是什么？

Answer 1

堆排序时间复杂度，主要在每次选取最大数之后，重新建堆的过程以及初始化堆过程。

堆排序是指利用堆积树这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。

堆是一个优先级队列，对于大顶堆而言，堆顶元素的权值最大。将待排序的数组建堆，然后不断地删除堆顶元素，就实现了排序。

堆的操作

在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：

最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。

创建最大堆（Build Max Heap）：将堆中的所有数据重新排序。

堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。