Python最小堆实现优化：如何缩短sift-down下沉逻辑的代码长度

优化后的完整实现如下，sift_down相关代码量减少60%以上，同时删除了冗余依赖和无用分支逻辑：

class MinHeap:
    def __init__(self, arr):
        self.arr = arr
        self.n = len(arr)

    def heapify(self):
        # 直接取完全二叉树最后一个非叶子节点索引，无需计算深度、不需要math依赖
        for i in range(self.n // 2 - 1, -1, -1):
            self.sift_down(i)

    def sift_down(self, i):
        while True:
            left = 2 * i + 1
            right = 2 * i + 2
            smallest = i
            # 直接找当前节点、左子、右子三者中的最小值索引
            if left < self.n and self.arr[left] < self.arr[smallest]:
                smallest = left
            if right < self.n and self.arr[right] < self.arr[smallest]:
                smallest = right
            # 当前节点已经是子树最小值，终止下沉
            if smallest == i:
                break
            # 交换后继续向下处理
            self.arr[i], self.arr[smallest] = self.arr[smallest], self.arr[i]
            i = smallest


nums = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
heap = MinHeap(nums)
heap.heapify()

核心优化点 #

• 删除了sift_down_level、is_left_child_exists、is_right_child_exists三个冗余方法，无需定义left_smaller/right_smaller这类临时标记变量，下沉逻辑全部收敛到同一个方法中
• 砍掉了原来的多分支判断：不需要分「左右子节点都更小/只有左更小/只有右更小」三种场景分别处理，只需要一次遍历找到三个节点中的最小值索引即可，if语句数量从原来的7个减少到3个
• 修复了原heapify方法的冗余问题：原来通过计算深度推导循环起始索引的方式会产生无用调用，完全二叉树最后一个非叶子节点固定为n//2 -1，循环范围更精准，同时省掉了math模块导入

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