I have these indexes: [3,1,1,2] which shows position for every element in the first list And I need to append these items to that corresponding indexes:
first_list = [Item("beer", 4), Item("steak", 1), Item("hamburger", 1), Item("donut", 3)]
to list, to be like in this particular order, so after the item is inserted on the index and the next item is again pointing to the same position, the first added moves to next the index and a new item is inserted to right position.
[ Item("hamburger", 1),Item("steak", 1), Item("donut", 3),Item("beer", 4)]
I need this algorithm to work in bigger lists so this is just an example.
Advertisement
Answer
The following builds a priority queue, where the “indices” indicate the priority of each item:
>>> indices = [3, 1, 1, 2]
>>> items = [("beer", 4), ("steak", 1), ("hamburger", 1), ("donut", 3)]
>>> from bisect import bisect_left
>>> prio = []
>>> new = []
>>> for i, item in zip(indices, items):
... index = bisect_left(prio, i)
... prio.insert(index, i)
... new.insert(index, item)
...
>>> new
[('hamburger', 1), ('steak', 1), ('donut', 3), ('beer', 4)]