使用heapq在Python中合并两个排序的数组

2021年5月16日17:11:26 发表评论 1,525 次浏览

给定两个排序数组, 任务是以排序方式合并它们。

例子:

Input :  arr1 = [1, 3, 4, 5]  
         arr2 = [2, 4, 6, 8]
Output : arr3 = [1, 2, 3, 4, 4, 5, 6, 8]

Input  : arr1 = [5, 8, 9]  
         arr2 = [4, 7, 8]
Output : arr3 = [4, 5, 7, 8, 8, 9]

这个问题已有解决方法, 请参考合并两个排序的数组链接。我们将使用python解决此问题heapq.merge()在一行代码中。

# Function to merge two sorted arrays
from heapq import merge
  
def mergeArray(arr1, arr2):
     return list (merge(arr1, arr2))
  
# Driver function
if __name__ = = "__main__" :
     arr1 = [ 1 , 3 , 4 , 5 ]  
     arr2 = [ 2 , 4 , 6 , 8 ]
     print mergeArray(arr1, arr2)

输出如下:

[1, 2, 3, 4, 4, 5, 6, 8]

heapq模块的属性?

该模块提供了堆队列算法(也称为优先级队列算法)的实现。

要创建堆, 请使用初始化为[]的列表, 或者可以通过函数heapify()将填充的列表转换为堆。提供了以下函数:

heapq.heappush(heap, item):将值项推入堆, 保持堆不变。

heapq.heappop(heap):弹出并从堆中返回最小的项, 从而保持堆不变。如果堆为空, 则会引发IndexError。要访问最小的项目而不弹出它, 请使用heap [0]。

heapq.heappushpop(heap, item):将项目推到堆上, 然后弹出并从堆中返回最小的项目。组合的操作比heappush()更有效地运行, 随后分别调用heappop()。

heapq.heapify(x):将列表x在线性时间内就地转换为堆。

heapq.merge(* iterables):将多个排序的输入合并到一个排序的输出中(例如, 合并来自多个日志文件的带有时间戳的条目)。返回排序后的值的迭代器。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

首先, 你的面试准备可通过以下方式增强你的数据结构概念:Python DS课程。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: