Python：最小堆交换计数

Question

虽然在 python 中已经提出和回答了很多关于堆实现的问题，但我无法找到任何关于索引的实际说明。那么，请允许我再问一个与堆相关的问题。

我正在尝试编写将值列表转换为最小堆并保存交换索引的代码。这是我目前所拥有的：

def mins(a, i, res):
    n = len(a)-1
    left = 2 * i + 1
    right = 2 * i + 2
    if not (i >= n//2 and i <= n):
        if (a[i] > a[left] or a[i] > a[right]):

            if a[left] < a[right]:
                res.append([i, left])
                a[i], a[left] = a[left], a[i]
                mins(a, left, res)
            
            else:
                res.append([i, right])
                a[i], a[right] = a[right], a[i]
                mins(a, right, res)

def heapify(a, res):
    n = len(a)
    for i in range(n//2, -1, -1):
        mins(a, i, res)
    return res


a = [7, 6, 5, 4, 3, 2]
res = heapify(a, [])

print(a)
print(res)

预期输出：

a = [2, 3, 4, 5, 6, 7]
res = [[2, 5], [1, 4], [0, 2], [2, 5]]

我得到的：

a = [3, 4, 5, 6, 7, 2]
res = [[1, 4], [0, 1], [1, 3]]

很明显，上面脚本中的索引有问题。可能是非常明显的东西，但我就是看不到。帮忙！

Answer 1

你的代码有一些错误：

在 heapify 中，具有 child 的第一个节点位于索引 (n - 2)//2，因此将其用作 range 的起始值.
在mins中，条件not (i >= n//2 and i <= n)不区分节点只有一个child或两个的情况。当 n 为奇数时， i==n//2 确实应该被允许。因为那时它还有一个左child。将 left 和 right 的值与 n 进行比较要容易得多。同样令人困惑的是，在 heapify 中你将 n 定义为 len(a)，而在 mins 中你将其定义为少一。这对于混淆代码的 reader 非常有用！

为避免代码重复（交换的两个块），引入一个新变量，该变量设置为 left 或 right，具体取决于哪个值较小。

这里更正：

def mins(a, i, res):
    n = len(a)
    left = 2 * i + 1
    right = 2 * i + 2
    if left >= n:
        return
    child = left
    if right < n and a[right] < a[left]:
        child = right
    if a[child] < a[i]:  # need to swap
        res.append([i, child])
        a[i], a[child] = a[child], a[i]
        mins(a, child, res)

def heapify(a, res):
    n = len(a)
    for i in range((n - 2)//2, -1, -1):
        mins(a, i, res)
    return res

Python：最小堆交换计数

Python: min heap swap count

python

indexing

heap

min-heap