Python 3.8中heapq.merge()是否返回最小堆？为何有误导性表现？

1. Python 3.8中的heapq.merge()是否返回最小堆？ #

答案是否。heapq.merge()的设计目的不是生成最小堆，它的作用是合并多个已按升序排序的输入迭代器，返回一个按升序排列的迭代器。它不会创建堆结构，也不对未排序的输入做整体排序。

2. 为何有时看似返回最小堆？ #

如果传入heapq.merge()的所有输入列表本身已经是升序排列的，那么它输出的迭代器会是整体升序的序列——这个结果和把所有元素放进最小堆后逐个弹出的结果一致，所以会看起来像是返回了最小堆，但本质上它只是有序序列，不是堆对象。

你的代码问题分析 #

看你提供的代码：

import heapq
L1 = [3,32,423,4,5,6,]
L2 = [32,66,6,32,4,8,0,]
L3 = heapq.merge(L1, L2)
print(L3)
print(list(L3))

你得到的混乱结果，核心原因是输入的L1和L2都不是升序排列的。heapq.merge()只会按每个输入自身的顺序去取元素做合并，不会先给输入排序。它的逻辑是维护每个输入的当前指针，每次选所有当前指针位置最小的元素，但因为你的输入本身无序，最终输出自然不是整体有序的。

如何得到最小堆结果？ #

如果你想要的是一个最小堆结构，或者整体有序的序列，可以这么做：

方法1：合并后转成最小堆 #

先把所有元素合并成一个列表，再用heapq.heapify()原地转成最小堆：

import heapq
L1 = [3,32,423,4,5,6,]
L2 = [32,66,6,32,4,8,0,]
merged_list = L1 + L2
heapq.heapify(merged_list)
print(merged_list)  # 这是一个最小堆结构
# 如果要逐个弹出最小元素（得到有序序列）：
while merged_list:
    print(heapq.heappop(merged_list), end=' ')

方法2：先排序输入再merge（得到有序序列） #

如果只是想要整体升序的序列，可以先给每个输入列表排序，再用heapq.merge()，此时输出的迭代器就是整体有序的：

import heapq
L1 = [3,32,423,4,5,6,]
L2 = [32,66,6,32,4,8,0,]
sorted_L1 = sorted(L1)
sorted_L2 = sorted(L2)
merged_sorted = list(heapq.merge(sorted_L1, sorted_L2))
print(merged_sorted)  # 输出整体升序的列表

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