0

I am trying to create a hip of event. Thus, I have define a class Event which is inherited by my different events.

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):
    ...

The value last_instant is the prio criteria, thus the heap is composed of tuples defined as follows:

(last_instant, Event)

However, I have events that are placed at the same last_instant, thus the heapq looks for the < implementation in the Event. I didn't yet implement it, but even if I did, I simply don't know how since some of the events do not have any criteria to differentiate which should be popped first from the heap.

How can I implement a heap where the order doesn't matter if the last_instant is the same?

On the other hand, if I have event of the same type (same class) at the same instant (same prio), I want to pop them together and treat them simultaneously.

The best way to achieve this that I can see is to pop all items at the same instant, store them in a list, and then treat them sequentially. Then go to the next instant. However, it doesn't seems compatible with heapq.

Thanks!

Mathieu
  • 5,410
  • 6
  • 28
  • 55
  • You might want to try using a different data structure than a heap. Maybe a sorted list of lists, where each element is a list of all the `Event`s with the same `last_instant`? – Green Cloak Guy Aug 06 '18 at 11:35
  • @GreenCloakGuy Sadly the time complexity is one of my priority. With a sorted list, it will be O(nlog(n)). With a heap, the push and pop actions only need O(log(n)). – Mathieu Aug 06 '18 at 11:38
  • Maybe a balanced binary tree, then? A heap isn't a great data structure for this, it doesn't seem. – Green Cloak Guy Aug 06 '18 at 11:40
  • @GreenCloakGuy I'm using the `heapq` python module. If I do not make a mistake, I think It is based on balanced binary tree. – Mathieu Aug 06 '18 at 11:41

1 Answers1

1

There's no reason you couldn't use the method you proposed: pop all items at the same instant, store them in a list, and then treat them sequentially. The basic idea is:

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

You'll want to convert that to real Python code, of course, but the basic idea works and is a perfectly valid use of a heap.

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351
  • Main issue is that apparently the heapq module do not allow elements with the same priority... The main asset of heapq is that it uses balanced binary tree heap, and thus is fast to pop and push. The while loop is really clear, and that would have been my approach, but it will raise an error. – Mathieu Aug 07 '18 at 07:49
  • @Mathieu Where does it say that heapq will not allow elements with the same priority? All my information says that it works just fine. – Jim Mischel Aug 07 '18 at 13:25
  • Hmm... I'm sorry you're right. The issue is slightly different. If I put tuples like `(1, 1)` in the heap it is fine, because they are equal. However, when using objects (class) like the following: `(prio, Class)` with prio being a number, it looks for the `<` implementation in the class, and this is what through an error. There is apparently no way to specify to the heap to look only for the first element of the tuple to do the prioritization and disregard the nexts. – Mathieu Aug 07 '18 at 13:59
  • Anyway, you're pseudo code is correct, and indeed there should be a way to do it. I'll keep digging, thanks :) – Mathieu Aug 07 '18 at 14:02
  • @Mathieu I think you'll find https://stackoverflow.com/questions/8875706/heapq-with-custom-compare-predicate useful. – Jim Mischel Aug 07 '18 at 14:05