python - 基于数组的 MinHeap

Question

我正在尝试实现一个将列表转换为 MinHeap 的函数。我看不出哪里出错了。

def min_heapify(nums):
    n = len(nums) - 1
    i = n // 2  # last parent

    while i >= 1:
        k = i
        v = nums[k]
        min_heap = False
        while not min_heap and 2 * k <= n:
            j = 2 * k
            if j + 1 <= n:
                if nums[j + 1] < nums[j]:
                    j += 1
            if nums[k] < nums[j]:
                min_heap = True
            else:
                nums[k] = nums[j]
                k = j
        nums[k] = v
        i -= 1

示例输入：

a_list = [0, 5, 2, 3, 4]
min_heapify(a_list)

输出（4 不正确）：

print("Min Heapify", a_list)  # Min Heapify [0, 2, 5, 3, 4]

标签： pythonalgorithmheapmin-heap

Answer 1

我认为你应该交换num[j]and num[k]，你刚刚分配的地方nums[k] = nums[j]：

def min_heapify(nums):
    n = len(nums) - 1
    i = n // 2  # last parent

    while i >= 1:
        k = i
        v = nums[k]
        min_heap = False
        while not min_heap and 2 * k <= n:
            j = 2 * k
            if j + 1 <= n:
                if nums[j + 1] < nums[j]:
                    j += 1
            if nums[k] < nums[j]:
                min_heap = True
            else:
                # HERE: Need to swap num[j] and num[k]
                [nums[j], nums[k]] = [nums[k], nums[j]]
                k = j
        nums[k] = v
        i -= 1

a_list = [0, 11, 5, 2, 3, 4, 7, 17, 6, 1]
min_heapify(a_list)
print(a_list)

# prints: [0, 1, 3, 2, 5, 4, 7, 17, 6, 11]