1

我有一个以这种格式存储的列表：[(int, (int, int)), ...]

对于第一种情况，我的代码看起来像这样。

heap.heappush(list_, (a, b))             # b is a tuple
while len(list_):
    temp = heap.heappop(list_)[1]

现在我理想的实现是

list_.append(a, b)                       # b is a tuple
while len(list_):
    list_.sort(key = lambda x: x[0])
    temp = list_.pop(0)[1]

第二种实现会导致我的代码的其他部分出现问题。是否有任何原因第二个不正确，我该如何纠正它以像 heapq 一样工作

编辑：我知道 heappop() 弹出最小值，这就是为什么我根据“a”对列表进行排序（我假设 heappop 也使用它）

4

1 回答 1

0

要使用 heapq，您必须知道 python 实现了最小堆。这意味着索引 0 处的元素始终是最小的。

这是您希望使用 heapq 实现的内容：

import heapq
from typing import Tuple

class MyObject:
 def __init__(self, a: int, b: Tuple(int, int)):
  self.a = a
  self.b = b
 
 def __lt__(self, other):
  return self.a < other.a

l = [MyObject(..,..), MyObject(..,..),..,MyObject(..,..)] # your list

heapq.heapify(l) # convert l to a heap
heapq.heappop(l) # retrieves and removes the smallest element (which lies at index 0)
# After popping the smallest element, the heap internally rearranges the elements to get the new smallest value to index 0. I.e. it maintaines the "heap variant" automatically and you don't need to explicitly sort!

注意：

  • 我不需要排序。堆本质上是一个半排序的结构
  • 我需要为我的对象创建一个专用类。这比使用元组的元组更干净，并且还允许我覆盖小于lt以便堆知道如何在内部创建树

这是为狂热的读者提供的更详细信息：D

当您使用堆时，您不需要显式排序。堆本质上是一种半排序拓扑，它（在 python heapq 的情况下）将最小元素保持在索引 0 处。但是，您不会看到下面的树结构（请记住，堆是其中每个父节点的树比它所有的孩子和后代都小）。

此外，您不需要逐个附加元素。而是使用 heapq.heapify()。这也将确保没有多余的 heapify-up/heapify-down 操作。否则，如果您的列表很大，您将遇到严重的运行时问题:)

于 2021-12-08T12:27:37.477 回答