Python最小堆实现错误排查及代码时间复杂度分析咨询

首先，我们来拆解你的代码出现的问题，以及如何修复：

一、堆结构构建错误（导致输出不符合预期） #

你的minHeap方法是从索引0开始顺序遍历每个节点调用heapify，这是错误的建堆方式。正确的小顶堆构建应该从最后一个非叶子节点开始，倒序向上遍历调整，原因如下：

• 叶子节点（索引大于len(heap)//2 -1）本身已经满足堆的性质，不需要调整；
• 如果从根节点开始顺序调整，下层未处理的节点会破坏上层已经调整好的堆结构，最终无法得到正确的小顶堆。

修正minHeap方法： #

def minHeap(self):
    # 计算最后一个非叶子节点的索引
    start_idx = len(self.heap) // 2 - 1
    # 从最后一个非叶子节点倒序遍历到根节点
    for i in range(start_idx, -1, -1):
        self.heapify(i)

修正后，运行代码会得到正确的小顶堆结构：[2, 5, 3, 10, 18, 15]（每个父节点都小于等于子节点，符合小顶堆性质）。

二、代码未实现完整的堆排序 #

你提到期望实现升序排序，但当前代码只完成了小顶堆的构建，并没有执行堆排序的核心步骤。完整的堆排序需要：

1. 构建小顶堆；
2. 重复将堆顶元素（当前最小值）与堆的最后一个元素交换；
3. 缩小堆的范围（排除已排序的元素），重新调整堆结构；
4. 直到整个数组有序。

新增完整堆排序方法： #

def heap_sort(self):
    # 先构建小顶堆
    self.minHeap()
    size = len(self.heap)
    for i in range(size-1, 0, -1):
        # 交换堆顶与当前堆的最后一个元素
        self.swap(0, i)
        # 缩小堆范围，重新调整堆
        self.heapify(0, i)

# 同时修改heapify方法，加入size参数限制堆的范围
def heapify(self, index, size=None):
    if size is None:
        size = len(self.heap) - 1
    left = 2 * index + 1
    right = 2 * index + 2
    minE = index
    if left <= size and self.heap[left] < self.heap[minE]:
        minE = left
    if right <= size and self.heap[right] < self.heap[minE]:
        minE = right
    if minE != index:
        self.swap(minE, index)
        self.heapify(minE, size)

调用heap_sort方法后，最终会得到升序排序结果：[2, 3, 5, 10, 15, 18]。

三、时间复杂度分析 #

1. 建堆过程的时间复杂度：O(n) #

堆构建过程中，每个节点的heapify操作时间复杂度为O(h)（h是节点的高度）。所有节点的高度之和是O(n)，因此整体建堆时间是线性的O(n)。

2. 完整堆排序的时间复杂度：O(nlogn) #

堆排序需要执行n-1次堆顶交换和堆调整操作，每次调整堆的时间复杂度是O(logn)（因为堆的高度是logn）。因此总时间复杂度为O(nlogn)，且最好、最坏、平均情况的时间复杂度都是O(nlogn)——因为堆排序的比较次数与初始序列的有序性无关。

内容的提问来源于stack exchange，提问作者Bhavesh818