代码之家  ›  专栏  ›  技术社区  ›  Mathieu

同等优先级的Heapq

  •  0
  • Mathieu  · 技术社区  · 6 年前

    我正在努力创造一个时髦的事件。因此,我定义了一个类 Event 这是由我的不同事件所继承的。

    class Event:
        def __init__(self, last_instant):
            self.last_instant = last_instant # That's the prio criteria
    
    class Event1(Event):
        def __init__(self, last_instant, value):
            Event.__init__(self, last_instant)
            self.value = value
    
    class Event2(Event):
        ...
    

    价值 last_instant 是prio条件,因此堆由定义如下的元组组成:

    (last_instant, Event)
    

    但是,我有一些事件放在同一个位置 最后一刻 ,因此 heapq 寻找 < 实施于 事件 . 我还没有实现它,但即使实现了,我也不知道如何实现,因为有些事件没有任何标准来区分哪些应该首先从堆中弹出。

    我如何实现顺序无关紧要的堆 最后一刻 是一样的吗?

    另一方面,如果我在同一时刻(同一优先级)有相同类型(同一类)的事件,我想将它们放在一起并同时处理它们。

    实现这一点的最好方法是同时弹出所有项目,将它们存储在一个列表中,然后按顺序处理它们。然后转到下一个瞬间。然而,它似乎与heapq不兼容。

    谢谢!

    1 回复  |  直到 6 年前
        1
  •  1
  •   Jim Mischel    6 年前

    没有理由你不能使用你建议的方法:在同一时刻弹出所有项目,将它们存储在一个列表中,然后按顺序处理它们。基本思想是:

    item = heap.pop()
    itemlist.push(item)
    while (heap not empty && heap.peek().priority == item.priority) {
        itemlist.push(heap.pop());
    }
    

    当然,您会希望将其转换为真正的Python代码,但基本思想是有效的,并且是对堆的完全有效的使用。