我正在处理一个关于从数组构建最小堆的问题。我有两种方法——第一种是递归，第二种是使用while循环。递归方法通过了在线评分器的测试，但while循环版本似乎不起作用。我在下面的代码中生成了一些随机的压力测试，发现这两种方法也给出了不同的答案。
我可以知道我的第二种方法有什么错误吗？问题如下：
输入格式输入的第一行包含一个整数。下一行包含空格整数。
限制1≤≤100000；0≤，≤−1；0≤0，1−1≤109。所有都是不同的。
输出格式输出的第一行应该包含一个整数——交换的总数。
必须满足条件0≤≤4。接下来的几行应该包含用于将数组转换为堆的交换操作。每个交换都由一对整数描述，即基于0的整数要交换的元素的索引。在按指定顺序应用所有交换后，数组必须成为一个堆，也就是说，对于0≤−1的每一个，以下条件必须为真：
- 如果2+1≤−1，则<2+1
- 如果2+2≤−1，则<2+2
请注意，输入数组的所有元素都是不同的。请注意，任何长度最多为4的交换序列，并且在该序列之后，初始数组将成为正确的堆，都将被评为正确的。
我的代码：
# python3
from random import randint
swaps = []
def sift_down(i, n, data):
min_index = i
left_child = 2*i + 1
right_child = 2*i + 2
if left_child < n and data[left_child] < data[min_index]:
min_index = left_child
if right_child < n and data[right_child] < data[min_index]:
min_index = right_child
if i != min_index:
swaps.append([i, min_index])
data[i], data[min_index] = data[min_index], data[i]
sift_down(min_index, n, data)
def build_heap(data):
n = len(data)
for i in range(n//2, -1, -1):
sift_down(i, n, data)
return swaps
# wrong answer using while loop instead of recursion
def build_heap2(data):
swap = []
for i in range(len(data)-1, 0, -1):
current_node = i
prev_node = i // 2 if i % 2 != 0 else i // 2 - 1
while data[prev_node] > data[current_node] and current_node != 0:
swap.append((prev_node, current_node))
data[prev_node], data[current_node] = data[current_node], data[prev_node]
current_node = prev_node
prev_node = current_node // 2 if current_node % 2 != 0 else current_node // 2 - 1
return swap
def main():
# n = int(input())
# data = list(map(int, input().split()))
# assert len(data) == n
while True:
n = randint(1, 100000)
data = []
data2 = []
for i in range(n):
data.append(randint(0, 10^9))
data2 = data.copy()
swaps = build_heap(data)
swaps2 = build_heap2(data2)
if swaps != swaps2:
print("recursion")
print(data[0], len(data), len(swaps))
print("loop:")
print(data2[0], len(data2), len(swaps2))
break
else:
print("success")
swaps = build_heap(data)
print(len(swaps))
for i, j in swaps:
print(i, j)
if __name__ == "__main__":
main()
您的build_heap2实现了一个不正确的想法。它从树的底部开始(正确)，但随后在尚未堆积的树的上部向上冒泡值(错误)。这不好。它不仅可以报告错误的交换数量，而且不会总是提供有效的堆。例如，对于[3, 1, 2, 4, 0]，交换后的结果仍然不是堆，因为值1最终是3的子级。
其目的是在树的底部建立小堆，在父节点的子节点变成堆后，该父节点中的值被向下筛选到这两个子堆中的任何一个子堆中。这是正确的，因为现在移动的值正在一个已经堆积的子树中移动。结果是，这两个小堆的父堆现在是有效堆本身的根。因此，在算法结束时，根将是有效堆的根。
因此，您不需要在树中向上交换值，而需要向下交换(选择值最小的子项)。
以下是更正后的版本：
def build_heap(data):
swap = []
# We can start at the deepest parent:
for i in range(len(data) // 2 - 1, -1, -1):
current_node = i
while True:
child_node = current_node * 2 + 1
if child_node >= len(data):
break
if child_node + 1 < len(data) and data[child_node + 1] < data[child_node]:
child_node += 1
if data[current_node] < data[child_node]:
break
# swap the current value DOWN, with the least of both child values
swap.append((child_node, current_node))
data[child_node], data[current_node] = data[current_node], data[child_node]
current_node = child_node
return swap
构建堆(至少)有两种方法。
O(N)解决方案从数据集的中间向后工作到开始，确保每个连续元素都是此时子树的正确根：
def build_heap_down(data):
n = len(data)
for subtree in range(n // 2 - 1, -1, -1):
sift_down(subtree, n, data)
另一个解决方案是O(N log N)，它只是将每个元素依次添加到一个更大的堆中：
def build_heap_up(data):
for new_element in range(1, n):
sift_up(new_element, data)
由于build_heap_up()在最坏的情况下是对数线性的(我认为这是反向排序的输入)，它可能不能满足您的分配的需要，因为它对交换数量施加了线性约束。尽管如此，还是值得做一些实验。也许这就是这次任务的重点。
def sift_up(elt, data):
while elt > 0:
parent = (elt - 1) // 2
if data[parent] <= data[elt]: return
swap(parent, elt, data)
elt = parent
def sift_down(elt, limit, data):
while True:
kid = 2 * elt + 1
if kid >= limit: return
if kid + 1 < limit and data[kid + 1] < data[kid]: kid += 1
if data[elt] <= data[kid]: return
swap(elt, kid, data)
elt = kid
这里的关键见解是，sift_up和sift_down都要求它们正在处理的数组是一个堆，除了要筛选的元素。sift_down从筛选的元素一直处理数组，因此在整个数组上正确处理需要向后处理。sift_up从一开始到筛选的元素都使用数组，因此迭代必须向前进行。
在我看来，你的build_heap是build_heap_down。尽管它使用递归，但它做的事情与我上面的循环(以及@trincot的版本)相同；使用尾部调用消除，函数末尾的递归总是可以变成一个简单的循环。(有些语言会自动执行这种程序转换，但Python不是其中之一。)
您的build_heap2是build_heap_up的错误版本，因为它是向后工作的，而不是向前工作的。这很容易解决。但不要指望它会产生相同的堆，更不用说相同的交换列表了。有许多可能的堆可以从给定的数字列表中构建，这就是为什么可以为build_heap而不是sort找到O(N)算法的原因。