堆排序一次的时间复杂度

堆排序（Heap Sort）是一种基于比较的排序算法，其基本原理是利用堆这种数据结构来进行操作。在堆排序中，时间复杂度主要关注的是排序过程中两个关键步骤：建堆和调整堆。

- **建堆**：建堆的过程的时间复杂度为O(n)，其中n是要排序的元素数量。这是因为建堆通常涉及到从最后一个非叶子节点开始，逐步向上调整每个节点，使其满足堆的性质（父节点大于或等于子节点）。

- **调整堆**：排序过程中每次选择堆顶元素（最大值或最小值，取决于是最大堆还是最小堆），并将其与最后一个元素交换，然后将剩余元素重新调整成堆。这个过程对于n个元素需要重复n-1次，因为每次调整都会使堆减少一个元素。调整堆的时间复杂度为O(log n)，因为它类似于二叉树的层次遍历。

- **整个排序过程**：由于每次调整堆后都需要对剩下的n-1个元素重新调整，所以总共需要执行n-1次调整堆操作。因此，总的调整堆部分的时间复杂度为O((n-1) * log n)。

综合起来，堆排序的一次性时间复杂度并不是简单相加，而是包括了建堆和多次调整堆。如果只看单次调整堆，那么时间复杂度是O(log n)；但如果我们考虑从头到尾整个排序过程，整体时间复杂度为O(n + (n-1) * log n)，简化后近似为O(n log n)。这是一般意义上的平均时间复杂度，最坏情况下的时间复杂度也相同。