时间戳

首页 > 解决方案 > heapify 和 heappush 有什么区别？哪个更好？

python - heapify 和 heappush 有什么区别？哪个更好？

问题描述

heapify 和 heapush 都将最小项目放在顶部，最低项目放在正确的位置。我不明白有什么区别和用法区别

import heapq
H = [21,1,45,78,3,5]
# Covert to a heap

# Add element
heapq.heappush(H,-100)
heapq.heappush(H,-98)
heapq.heappush(H,-1)
print(H)
heapq.heapify(H)

print(H)


# output: [-100, -98, 21, -1, 3, 5, 45, 78, 1]
# [-100, -98, 5, -1, 3, 21, 45, 78, 1]

标签： pythonheap

解决方案

heappush和之间有很多不同之处heapify。

  1. heappush假设数组（H在你的情况下）已经是一个堆。heapify不 -H只需要是一个列表。请注意，在您的示例中，在执行三个命令H之前，您的数据结构不是堆。heappush（例如，H开头为[21,1,45,78,3,5]，但第一项21大于第二项1，这违反了堆的定义。）因此，命令H之后也不是堆。heappush（H变为[-100, -98, 21, -1, 3, 5, 45, 78, 1]but 第 3 项21大于第 6 项5，这也违反了堆的定义。） 之后heapify，5和21项交换了位置，H然后是正确的堆。
  2. heappush向堆中添加一个新值。heapify不添加值 - 它重新排列列表中的值。
  3. 您可以通过创建一个空堆然后调用heappush您要添加的每个项目来构建一个堆，或者您可以按任何顺序创建一个项目列表然后调用heapify该列表。该heappush方法的时间复杂度为 O(n * log(n))，其中n是堆的结束大小，而该heapify方法的复杂度为 O(n)，显着降低。例如，如果您正在创建一个包含一百万个项目的堆，则该heappush方法最多可以使用20,000,000操作顺序，而该heapify方法最多只能使用1,000,000操作顺序。这是一个20不同的因素。当然，操作不完全一样，实际数字略有不同，所以实际因素会有所不同，但heapify几乎肯定会更快。
  4. 构建堆的heappush方法需要许多单独的语句或某种循环来添加项目。该heapify方法仅要求列表存在。因此，该heapify方法很可能会使用更少的代码行和更少的代码复杂度。（在for代码中添加循环会增加另一层复杂性，这可能会导致更多错误。）

总之，heapify在列表上做几乎总是比创建一个空列表并添加许多项目更好的选择heappush。如果你只是添加一些项目，heappush可能会更好。

推荐阅读